# streaming algorithms

Published articles for streaming algorithms.

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.

## The Complexity of Communication

DevFeed: [The Complexity of Communication](<https://devfeed.tech/articles/the-complexity-of-communication-40369.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2014/11/10/the-complexity-of-communication/>)

Published: 2014-11-10T09:00:25Z

Content type: tutorial

Language: en

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

Topics: [Computer science](<https://devfeed.tech/topics/computer-science.md>), [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Streaming](<https://devfeed.tech/topics/streaming.md>), [circuit](<https://devfeed.tech/topics/circuit.md>)

Tags: [communication](<https://devfeed.tech/tags/communication.md>), [communication-complexity](<https://devfeed.tech/tags/communication-complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [fourier-analysis](<https://devfeed.tech/tags/fourier-analysis.md>), [information-theory](<https://devfeed.tech/tags/information-theory.md>), [log-rank-conjecture](<https://devfeed.tech/tags/log-rank-conjecture.md>), [lower-bounds](<https://devfeed.tech/tags/lower-bounds.md>), [matrices](<https://devfeed.tech/tags/matrices.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [theory](<https://devfeed.tech/tags/theory.md>)

### AI overview

This tutorial introduces communication complexity: how much information two parties must exchange to jointly compute a function of separate inputs. It presents the basic two-player model and explains the subject's use in proving lower bounds, including applications to circuit design and streaming algorithms.

### Source excerpt

satellite One of the most interesting questions posed in the last thirty years of computer science is to ask how much "information" must be communicated between two parties in order for them to jointly compute something. One can imagine these two parties living on distant planets, so that the cost of communicating any amount of information is very expensive, but each person has an integral component of the answer that the other does not.

## 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.

## Probabilistic Bounds -- A Primer

DevFeed: [Probabilistic Bounds -- A Primer](<https://devfeed.tech/articles/probabilistic-bounds-a-primer-40312.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2013/04/15/probabilistic-bounds-a-primer/>)

Published: 2013-04-15T11:14:32Z

Content type: tutorial

Language: en

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

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [math](<https://devfeed.tech/topics/math.md>), [Learning](<https://devfeed.tech/topics/learning.md>), [Streaming](<https://devfeed.tech/topics/streaming.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [chebyshev](<https://devfeed.tech/tags/chebyshev.md>), [chernoff](<https://devfeed.tech/tags/chernoff.md>), [chernoff-bound](<https://devfeed.tech/tags/chernoff-bound.md>), [inequality](<https://devfeed.tech/tags/inequality.md>), [learning-theory](<https://devfeed.tech/tags/learning-theory.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [markov](<https://devfeed.tech/tags/markov.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [probabilistic](<https://devfeed.tech/tags/probabilistic.md>), [probabilistic-method](<https://devfeed.tech/tags/probabilistic-method.md>), [probability-theory](<https://devfeed.tech/tags/probability-theory.md>), [random-variables](<https://devfeed.tech/tags/random-variables.md>), [streaming](<https://devfeed.tech/tags/streaming.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [variance](<https://devfeed.tech/tags/variance.md>)

### AI overview

This tutorial introduces probabilistic bounds used in algorithm analysis, machine learning theory, randomized algorithms, and streaming algorithms. It focuses on the Chernoff bound and presents simpler bounds from Markov's and Chebyshev's inequalities, including short proofs.

### Source excerpt

Probabilistic arguments are a key tool for the analysis of algorithms in machine learning theory and probability theory. They also assume a prominent role in the analysis of randomized and streaming algorithms, where one imposes a restriction on the amount of storage space an algorithm is allowed to use for its computations (usually sublinear in the size of the input). While a whole host of probabilistic arguments are used, one theorem in particular (or family of theorems) is ubiquitous: the Chernoff bound.