- Atlas
- Computer Science
- Streaming Algorithms
Streaming Algorithms
A streaming algorithm is a procedure that reads its input once, from beginning to end, in the order the data arrives, and must answer questions about that input while using memory far smaller than the input itself.
10 frameworks, from 1985 to today · Algorithms · Computer Science
- Probabilistic Counting and Cardinality Sketches 1985-Present
- Communication complexity 1996-Present
- Frequency Moments and Linear Sketches 1996-Present
- Turnstile and Dynamic-Stream Models 2000-Present
- Quantile and Order-Statistics Summaries 2001-Present
- Sliding-Window and Time-Decay Models 2002-Present
- Count–min sketch 2005-Present
- Graph Streaming and Sparsification 2005-Present
- Mergeable Summaries and Distributed Streaming 2005-Present
- Learned and Adaptive Streaming 2018-Present
Overview
A streaming algorithm is a procedure that reads its input once, from beginning to end, in the order the data arrives, and must answer questions about that input while using memory far smaller than the input itself1. The input—a "stream"—might be billions of network packets, clicks in a search log, or edges of a social network too large to store2. The algorithm sees each item once and, in most models, cannot go back1. What makes the field distinctive is the resource it rations: not time, but space1. A streaming algorithm is judged by how much working memory it needs, and the central drama of the field is the discovery that many questions can be answered, at least approximately, with astonishingly little memory—and that some cannot be answered at all without a lot of it.
That tension—between what a tiny amount of memory can and cannot do—is what turned a collection of practical tricks into a theory with lower bounds, models, and a canon of its own.
Counting a huge file with a handful of counters
The practical roots lie in databases and networks. In the 1970s and 1980s, database systems needed to estimate quantities over tables too large to scan repeatedly: how many distinct values does this column hold? What is the median? The classic answer for distinct counting was sorting or hashing everything, which needs memory proportional to the number of distinct items. A different idea appeared in the early 1980s: instead of storing items, store a sketch—a small summary that can be updated as items arrive and queried later.
Philippe Flajolet and G. Nigel Martin's 1985 paper on probabilistic counting is the landmark. Their insight was to hash each incoming item to a random binary string and track the longest run of leading zeros seen. If you see a string with k leading zeros, you have probably seen on the order of 2^k distinct items, because such strings are rare. A handful of registers and a hash function thus estimate the number of distinct elements—the cardinality—of a stream using memory logarithmic in the answer rather than linear. The idea was elegant but the estimator was noisy; refinements over the following decades (notably by Marianne Durand and Philippe Flajolet in 2003, and later the "HyperLogLog" sketch, also due to Flajolet and colleagues in 2007) made it accurate enough to become a standard tool in databases and web analytics. The pattern set here—trade exactness for a small, mergeable summary—recurred throughout the field.
The theory crystallizes: frequency moments and lower bounds
The 1990s turned these tricks into a discipline. The pivotal paper is by Noga Alon, Yossi Matias, and Mario Szegedy, published in 1996 (with a 1999 journal version), which asked a clean theoretical question: given a stream of items, estimate the frequency moments. The k-th frequency moment is the sum over distinct items of (how many times that item appeared)^k1. The zeroth moment counts distinct items; the first is just the stream length; the second measures how "skewed" the frequencies are—useful for detecting heavy hitters and join sizes in databases.
Alon, Matias, and Szegedy gave algorithms using linear sketches: maintain a small vector that is a linear function of the stream, updated by adding a fixed vector for each item. Random projections of this kind let one estimate moments with memory polylogarithmic in the stream length. Crucially, they also proved lower bounds: some moments, like the second, need only logarithmic space, while others provably require polynomial space. This was the birth of streaming lower bounds—proofs that no algorithm, however clever, can do the job in too little memory1.
The lower-bound technique drew on a neighbouring field1. Communication complexity, developed by Andrew Yao in 1979, studies how many bits two parties must exchange to compute a function when each holds part of the input3. A streaming algorithm can be recast as a communication protocol—split the stream between two players—so a communication lower bound becomes a space lower bound. This bridge, made explicit in the 1990s and sharpened in later surveys, gave the field its main tool for proving impossibility. The 2005 survey by S. Muthukrishnan helped codify the area, and a 2005 paper by Piotr Indyk and David Woodruff gave tight bounds for many linear-algebraic problems in the stream, showing that even approximating norms and solving regression could be done in small space—or provably not.
The turnstile model and the algebra of sketches
Early streams only added items. A more general and harder model, the turnstile model, allows items to be deleted: the stream is a sequence of signed updates, and the algorithm must track the net effect1. This matters for real systems—a network flow counter must decrement when a connection closes. The turnstile model forced the theory to be precise about what a sketch can represent, and it produced some of the field's most beautiful results.
The count-min sketch, introduced by Graham Cormode and S. Muthukrishnan in 2005, is the canonical frequency counter: a small two-dimensional array of counters, with several hash functions, that estimates how often each item has appeared, always overestimating and never underestimating. It is simple, fast, and mergeable, and it became ubiquitous in networking and databases. Around the same period, the AMS sketch (from Alon–Matias–Szegedy) and related linear sketches were shown to support deletions naturally, because linearity means updates can be added and subtracted. The 2000s saw a systematic theory of mergeable summaries: sketches that can be combined, so that summaries computed on separate machines or time windows can be added together. This is what makes streaming algorithms work in distributed settings—each node sketches its share, and the sketches are merged.
Order statistics, quantiles, and the shape of a distribution
Counting frequencies is one thing; recovering the distribution is another. A stream may need its median, its 90th percentile, or a summary of its value distribution. Exact quantiles require storing the data, so the field developed quantile summaries: small structures that answer "what value is at rank r?" within a guaranteed error.
The Greenwald–Khanna algorithm (2001) gave deterministic guarantees for quantile estimation over a stream with memory logarithmic in the stream length and inversely proportional to the desired accuracy. A different and widely used approach, the t-digest (Ted Dunning, 2019), trades formal worst-case guarantees for excellent accuracy at the tails, which is where monitoring systems care most. These summaries, like frequency sketches, are mergeable, and they became standard in observability and analytics systems that must summarize billions of latency measurements in real time.
Windows, decay, and the problem of the recent past
Real streams are not stationary: what happened an hour ago matters more than what happened last year. The field responded with sliding-window models, where only the last W items count, and time-decay models, where older items are weighted less. The sliding-window model, formalized in the early 2000s (notably by Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani in 2002), asks algorithms to maintain summaries over a moving window without storing the window. This is harder than the static case because items expire, and a sketch must "forget" gracefully. The exponential-histogram technique—keeping summaries at exponentially increasing granularities—became a standard way to answer windowed queries with logarithmic memory. These ideas underpin real-time monitoring, where dashboards must reflect the last few minutes of traffic.
Graphs, and the move beyond counting
By the 2010s, attention shifted from sequences of items to graph streams: edges arriving one at a time, representing a network too large to store. Can you count connected components, estimate the size of the largest component, or test bipartiteness without keeping the edges? A landmark result is the sparsification approach: a small random sample of edges can preserve connectivity and cut structure, so a graph stream can be summarized by a sparse subgraph. The 2000s and 2010s produced algorithms for counting triangles, estimating clustering coefficients, and computing spanning forests in small space, often with lower bounds showing the limits. This work connected streaming to graph algorithms and to the study of massive networks.
The present: learned, adaptive, and still bounded
The most recent turn is toward adaptivity and learning. Classical streaming algorithms assume the input is arbitrary—worst-case—and guarantee performance against any stream. But real streams have structure: they are skewed, repetitive, or drawn from a known distribution. Learned and adaptive streaming algorithms use a model of the data—perhaps a predictor trained on past streams—to choose parameters, allocate memory, or skip work, while still guaranteeing correctness if the model is wrong. This mirrors a broader movement in algorithms toward learning-augmented methods, and it raises the field's enduring question in a new form: how much can you assume about your data before your guarantees become hollow?
Today the field's core tools—linear sketches, count-min, HyperLogLog, quantile summaries, windowed histograms—are embedded in databases, network monitors, and analytics platforms. The theory that grew around them, with its communication-complexity lower bounds and its precise models of what memory can buy, remains the field's intellectual spine1. What is still open is the frontier the field has always faced: the gap between what small memory can provably do and what practitioners need, especially for the graph and adaptive problems where the lower bounds are still being mapped.
References
- Streaming algorithm (introduction, Data stream model, Frequency moments, Lower bounds, Turnstile and cash register models), Wikipedia
- Data stream mining, Wikipedia
- Communication complexity, Wikipedia
The frameworks of Streaming Algorithms
Each framework is a way of working the field has used: when it held, and the question it answers.
- 1985-Present
Probabilistic Counting and Cardinality Sketches
How many distinct items are in this stream?
- 1996-Present
Communication complexity
How many bits must two parties exchange to compute a function?
- 1996-Present
Frequency Moments and Linear Sketches
How skewed are the frequencies in a stream?
- 2000-Present
Turnstile and Dynamic-Stream Models
How can we track net counts when items can be deleted?
- 2001-Present
Quantile and Order-Statistics Summaries
What value sits at a given rank in the stream?
- 2002-Present
Sliding-Window and Time-Decay Models
How do we summarize only the most recent data?
- 2005-Present
- 2005-Present
Graph Streaming and Sparsification
What global structure does a stream of edges have?
- 2005-Present
Mergeable Summaries and Distributed Streaming
How can summaries from many machines be combined?
- 2018-Present
Learned and Adaptive Streaming
Can a learned model of the data save memory?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Turnstile and Dynamic-Stream Models grew out of Frequency Moments and Linear Sketches
The linear sketches introduced for frequency moments were naturally additive, so the turnstile model grew directly out of them: signed updates could be handled because the sketch was a linear function of the stream.
Carried by Noga Alon; Yossi Matias; Mario Szegedy.
Frequency Moments and Linear Sketches influenced by Probabilistic Counting and Cardinality Sketches
Alon, Matias, and Szegedy's frequency-moment algorithms built on the probabilistic-counting tradition of estimating aggregate statistics from hashed sketches, with the zeroth moment being exactly the distinct-count problem Flajolet and Martin had addressed.
Carried by Noga Alon; Yossi Matias; Mario Szegedy.
Count–min sketch influenced by Frequency Moments and Linear Sketches
Cormode and Muthukrishnan's count-min sketch took up the frequency-estimation question posed by the frequency-moments work, providing a simple hashed-counter alternative to the linear-sketch estimators for point queries.
Carried by Graham Cormode; S. Muthukrishnan.
Graph Streaming and Sparsification influenced by Frequency Moments and Linear Sketches
Graph-streaming algorithms for connectivity and cuts reused the linear-sketch and sparsification toolkit, treating edge arrivals as updates to a sketch and sampling edges to preserve cut structure.
Mergeable Summaries and Distributed Streaming influenced by Frequency Moments and Linear Sketches
Mergeable summaries rest on the linearity of AMS-style sketches: because a sketch is a linear function of the stream, sketches computed on separate partitions can simply be added, which is the basis of distributed streaming.
Carried by Noga Alon; Yossi Matias; Mario Szegedy.
Sliding-Window and Time-Decay Models grew out of Turnstile and Dynamic-Stream Models
The sliding-window model was formulated as a restriction of the dynamic-stream setting: Datar, Gionis, Indyk, and Motwani required summaries to be maintained over only the most recent W updates, making expiry the central difficulty.
Carried by Mayur Datar; Aristides Gionis; Piotr Indyk.
Mergeable Summaries and Distributed Streaming influenced by Quantile and Order-Statistics Summaries
Quantile summaries such as Greenwald–Khanna were shown to be mergeable, so that summaries from separate machines could be combined; this mergeability became a central requirement in the theory of distributed streaming summaries.
Carried by Michael Greenwald; Sanjeev Khanna.
Mergeable Summaries and Distributed Streaming influenced by Count–min sketch
The count-min sketch was explicitly designed to be mergeable, with counters combined by addition, and this property was promoted as what makes sketches usable across distributed nodes and time windows.
Carried by Graham Cormode; S. Muthukrishnan.
Learned and Adaptive Streaming influenced by Probabilistic Counting and Cardinality Sketches
Learned streaming algorithms keep the sketch-based, sublinear-memory framing of the field's founding work but replace worst-case hashing assumptions with learned models of the data distribution.
Beyond the field
Where Streaming Algorithms's ideas came from in other fields, and what they led to there: the strongest 12 of 14 links.
Communication complexity grew out of Computational Complexity Theory in Complexity Theory
Communication complexity grew directly out of computational complexity theory, with Yao's 1979 paper framing two-party communication as a complexity measure and later work applying it to streaming lower bounds.
Carried by Andrew Yao.
Communication complexity grew out of Computational Complexity Theory in Theory Of Computation
Communication complexity was founded by Yao as a branch of computational complexity theory, adapting complexity-theoretic lower-bound questions to two-party communication problems.
Carried by Andrew Yao.
Sliding-Window and Time-Decay Models grew out of Streaming algorithm in Randomized Algorithms
Sliding-window and time-decay models are streaming algorithms, extending the streaming model with recency-weighted or windowed queries.
Graph Streaming and Sparsification grew out of Streaming algorithm in Randomized Algorithms
Graph streaming is a specialization of the general streaming-algorithm model, applying its single-pass, sublinear-space constraints to graph problems. The graph-streaming literature explicitly frames itself as streaming algorithms for graphs.
Mergeable Summaries and Distributed Streaming grew out of Streaming algorithm in Randomized Algorithms
Mergeable summaries are a specialization of streaming algorithms, adding a merge operation to the sketch model so summaries computed on separate streams can be combined. The framework is unthinkable without the streaming-algorithm model it extends.
Learned and Adaptive Streaming grew out of Streaming algorithm in Randomized Algorithms
Learned and adaptive streaming grew directly out of streaming algorithms, replacing hand-designed sketches with learned models while keeping the single-pass, sublinear-space setting. The framework is a refinement of the streaming-algorithm model.
Communication complexity influenced by Distributed Complexity and Communication Lower Bounds in Distributed Algorithms
Distributed-computing lower bounds and message-passing models provided the two-party abstraction and round structure that communication complexity formalised and then fed back into streaming lower bounds.
Communication complexity influenced by Circuit complexity in Parallel Algorithms
Circuit-complexity techniques, particularly lower bounds via restrictions and communication arguments, were adapted to prove communication lower bounds and later streaming lower bounds.
Frequency Moments and Linear Sketches influenced by Matrix and Vector Algebra in Linear Algebra
Linear sketches are built on linear-algebraic constructions such as random projections and inner-product identities, which the frequency-moment algorithms used to estimate moments from linear measurements.
Turnstile and Dynamic-Stream Models influenced Data Stream Mining in Data Mining
Data stream mining developed alongside and drew on turnstile-style dynamic stream models, adopting their update semantics for mining over evolving data streams.
Quantile and Order-Statistics Summaries influenced by Order-statistics and quantile inference in Nonparametric Statistics
Quantile and order-statistics summaries in streams took the statistical concept of order statistics and quantile estimation and adapted it to single-pass, bounded-memory computation.
Graph Streaming and Sparsification influenced by Spectral graph theory in Graph Algorithms
Spectral graph theory supplied the spectral sparsification concept, notably Spielman and Teng's work on spectral sparsifiers, which graph-streaming sparsification methods took up and adapted to the streaming setting.
Carried by Daniel A. Spielman; Shang-Hua Teng.

Streaming Algorithms is a planet in Nousfarer
Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.
Land on Streaming AlgorithmsRelated fields
Fields its ideas are linked to
- Randomized Algorithms 4 links
- Data Mining 2 links
- Linear Algebra 1 link
- Algorithms 1 link
- Distributed Algorithms 1 link
- Graph Algorithms 1 link
- Parallel Algorithms 1 link
- Nonparametric Statistics 1 link
- Complexity Theory 1 link
- Theory Of Computation 1 link
More in Algorithms
- Algorithms
- Approximation Algorithms
- Computational Geometry
- Data Structures
- Distributed Algorithms
- Graph Algorithms
- Online Algorithms
- Parallel Algorithms
- Parameterized Algorithms
- Randomized Algorithms
- String Algorithms
See where Streaming Algorithms sits on the Map of Human Knowledge