# streaming data

Published articles for streaming data.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Finding the majority element of a stream

DevFeed: [Finding the majority element of a stream](<https://devfeed.tech/articles/finding-the-majority-element-of-a-stream-40379.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/03/09/finding-the-majority-element-of-a-stream/>)

Published: 2015-03-09T09:00:11Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Python](<https://devfeed.tech/topics/python.md>), [data](<https://devfeed.tech/topics/data.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [counter](<https://devfeed.tech/tags/counter.md>), [data-mining](<https://devfeed.tech/tags/data-mining.md>), [frequency-moments](<https://devfeed.tech/tags/frequency-moments.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [pair](<https://devfeed.tech/tags/pair.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [space](<https://devfeed.tech/tags/space.md>), [stream](<https://devfeed.tech/tags/stream.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [streaming-data](<https://devfeed.tech/tags/streaming-data.md>), [sublinear-space](<https://devfeed.tech/tags/sublinear-space.md>)

### AI overview

This article presents a Python algorithm for finding the value that occurs more than half the time in a massive data stream. It explains the pairing-based correctness argument, single-pass operation, O(log(n) + log(m)) space usage, the necessity of the majority guarantee, and a k-counter generalization for detecting frequent items.

### Source excerpt

Problem: Given a massive data stream of $ n$ values in $ \{ 1, 2, \dots, m \}$ and the guarantee that one value occurs more than $ n/2$ times in the stream, determine exactly which value does so. Solution: (in Python) def majority(stream): held = next(stream) counter = 1 for item in stream: if item == held: counter += 1 elif counter == 0: held = item counter = 1 else: counter -= 1 return held Discussion: Let's prove correctness.

## Reservoir Sampling

DevFeed: [Reservoir Sampling](<https://devfeed.tech/articles/reservoir-sampling-40325.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/07/05/reservoir-sampling/>)

Published: 2013-07-05T10:00:49Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Python](<https://devfeed.tech/topics/python.md>), [data](<https://devfeed.tech/topics/data.md>), [datasets](<https://devfeed.tech/topics/datasets.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [big-data](<https://devfeed.tech/tags/big-data.md>), [generator](<https://devfeed.tech/tags/generator.md>), [induction](<https://devfeed.tech/tags/induction.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [random](<https://devfeed.tech/tags/random.md>), [randomized-algorithm](<https://devfeed.tech/tags/randomized-algorithm.md>), [reservoir-sampling](<https://devfeed.tech/tags/reservoir-sampling.md>), [sample](<https://devfeed.tech/tags/sample.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [streaming-data](<https://devfeed.tech/tags/streaming-data.md>), [streams](<https://devfeed.tech/tags/streams.md>)

### AI overview

This tutorial explains reservoir sampling for selecting an item uniformly at random from a data stream whose size is unknown or too large to store in memory. Its Python algorithm keeps one item and replaces it at step k with probability 1/k, with an induction-based proof of uniform selection.

### Source excerpt

Problem: Given a data stream of unknown size $ n$, pick an entry uniformly at random. That is, each entry has a $ 1/n$ chance of being chosen. Solution: (in Python) import random def reservoirSample(stream): for k,x in enumerate(stream, start=1): if random.random() < 1.0 / k: chosen = x return chosen Discussion: This is one of many techniques used to solve a problem called reservoir sampling. We often encounter data sets that we'd like to sample elements from at random.

## Streaming Median

DevFeed: [Streaming Median](<https://devfeed.tech/articles/streaming-median-40277.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/06/14/streaming-median/>)

Published: 2012-06-14T22:03:55Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Streaming](<https://devfeed.tech/topics/streaming.md>), [Python](<https://devfeed.tech/topics/python.md>), [Algorithms](<https://devfeed.tech/topics/algorithms.md>), [generators](<https://devfeed.tech/topics/generators.md>), [iteration](<https://devfeed.tech/topics/iteration.md>), [Programming](<https://devfeed.tech/topics/programming.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [big-data](<https://devfeed.tech/tags/big-data.md>), [data-analysis](<https://devfeed.tech/tags/data-analysis.md>), [element](<https://devfeed.tech/tags/element.md>), [generators](<https://devfeed.tech/tags/generators.md>), [implementation](<https://devfeed.tech/tags/implementation.md>), [infinite](<https://devfeed.tech/tags/infinite.md>), [input](<https://devfeed.tech/tags/input.md>), [iteration](<https://devfeed.tech/tags/iteration.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [median](<https://devfeed.tech/tags/median.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [sequence](<https://devfeed.tech/tags/sequence.md>), [streaming](<https://devfeed.tech/tags/streaming.md>), [streaming-data](<https://devfeed.tech/tags/streaming-data.md>), [yield](<https://devfeed.tech/tags/yield.md>)

### AI overview

This tutorial presents a Python generator that approximates the median of a potentially infinite integer sequence using constant space. The algorithm adjusts its current estimate by one for each input value that is above or below the estimate, and the article discusses how changing stream distributions affect the result.

### Source excerpt

Problem: Compute a reasonable approximation to a "streaming median" of a potentially infinite sequence of integers. Solution: (in Python) def streamingMedian(seq): seq = iter(seq) m = 0 for nextElt in seq: if m > nextElt: m -= 1 elif m < nextElt: m += 1 yield m Discussion: Before we discuss the details of the Python implementation above, we should note a few things. First, because the input sequence is potentially infinite, we can't store any amount of information that is increasing in the length of the sequence.