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

still a working view ended · each leads to its entry below

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

  1. Streaming algorithm (introduction, Data stream model, Frequency moments, Lower bounds, Turnstile and cash register models), Wikipedia
  2. Data stream mining, Wikipedia
  3. 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.

  1. 1985-Present
  2. 1996-Present

    Communication complexity

    How many bits must two parties exchange to compute a function?

    Fly to its tower in Nousfarer

  3. 1996-Present
  4. 2000-Present

    Turnstile and Dynamic-Stream Models

    How can we track net counts when items can be deleted?

    Fly to its tower in Nousfarer

  5. 2001-Present

    Quantile and Order-Statistics Summaries

    What value sits at a given rank in the stream?

    Fly to its tower in Nousfarer

  6. 2002-Present

    Sliding-Window and Time-Decay Models

    How do we summarize only the most recent data?

    Fly to its tower in Nousfarer

  7. 2005-Present

    Count–min sketch

    How often has each item appeared?

    Fly to its tower in Nousfarer

  8. 2005-Present

    Graph Streaming and Sparsification

    What global structure does a stream of edges have?

    Fly to its tower in Nousfarer

  9. 2005-Present
  10. 2018-Present

    Learned and Adaptive Streaming

    Can a learned model of the data save memory?

    Fly to its tower in Nousfarer

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.

Probabilistic Counting and Cardinalit…Communication complexityFrequency Moments and Linear SketchesTurnstile and Dynamic-Stream ModelsQuantile and Order-Statistics Summari…Sliding-Window and Time-Decay ModelsCount–min sketchGraph Streaming and SparsificationMergeable Summaries and Distributed S…Learned and Adaptive Streaming

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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Streaming Algorithms sits on the Map of Human Knowledge