# Streaming model (algorithms)
The streaming model is a computational model in which input arrives as a sequential stream and an algorithm with small memory must process it in one or a few passes. Each item is observed once, per-item processing time must be low, memory must be sublinear in the stream length, and a valid answer must be available at any time, even for nonstationary streams.[1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/) Formally, a streaming algorithm reading a stream of length \( m \) over a universe of size \( n \) may store only \( O(\log^{c}(nm)) \) bits for a fixed constant \( c \), a polynomial in \( \log n \) and \( \log m \).[2](https://www.cs.toronto.edu/~anikolov/CSC473W20/Lectures/streaming.pdf) The goal is a good approximation of a function of the stream, such as a frequency moment or the set of frequent items, using space far below what storing the data would require.[3](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes3.pdf)
| Key fact | Value |
|---|---|
| Core constraints | One pass, low per-item time, sublinear memory, answers available at any time[1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/) |
| Memory bound | \( O(\log^{c}(nm)) \) bits for fixed \( c \)[2](https://www.cs.toronto.edu/~anikolov/CSC473W20/Lectures/streaming.pdf) |
| Main model variants | Cash-register (insertions only) and turnstile (insertions and deletions)[3](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes3.pdf) |
| \( F_{2} \) estimation | \( O((1/\epsilon^{2})\log(1/\delta)\log n) \) bits via the AMS sketch[4](https://arxiv.org/pdf/2609.17286) |
| Turnstile \( F_{p} \), \( 0 < p \le 2 \) | \( \Theta(\epsilon^{-2}\log(mn)) \) bits, necessary and sufficient[5](https://www.ccs.neu.edu/home/viola/papers/BVWY-stream.pdf) |
| Count-Min sketch | Width \( w \ge \lceil e/\epsilon \rceil \), depth \( d \ge \lceil \ln(1/\delta) \rceil \)[1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/) |
| HyperLogLog | Standard error \( 1.04/\sqrt{m} \); \( 1.5 \) kB estimates cardinalities beyond \( 10^{9} \) at about 2% accuracy[6](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf) |
## How it works
A streaming algorithm \( A \) receives a stream \( S = s_{1}, \ldots, s_{m} \) over a universe \( U \) of size \( n \), reads it in arrival order, cannot re-read the input, and in most cases reads the data only once.[3](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes3.pdf) Elements of the universe occupy a fixed number of bits each, for example 32-bit IP addresses, and the algorithm computes a function continually on every prefix of the stream.[7](https://www.cs.cmu.edu/~15750/notes/streaming.pdf) In the database-oriented formulation, data does not take the form of persistent relations but arrives in multiple, continuous, rapid, time-varying streams.[8](https://dl.acm.org/doi/10.1145/543613.543615)
Two model variants dominate the theory. In the cash-register model, each stream item is an element of the universe, inserted in arbitrary order; counts only grow. In the turnstile model, items are \( (x, \pm) \) pairs that add or delete \( x \) from a multiset, so the stream is dynamic.[3](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes3.pdf) Any turnstile streaming algorithm can be turned into an algorithm based solely on updates of linear sketches, which is why insertion-only models are more challenging for streaming communication protocols.[9](https://www.irif.fr/~magniez/PAPIERS/bkm-toct18.pdf) The equivalence between turnstile streaming and linear sketching holds when the algorithm works for arbitrarily long streams with arbitrarily large coordinates; if either the stream length or the maximum stream value is substantially restricted, there exist problems where linear sketching is exponentially harder than turnstile streaming.[10](https://dl.acm.org/doi/10.1145/3357713.3384278)
## How it is done
A sketch is a data structure plus accompanying algorithms that read a stream and store sufficient information to answer one or more predefined queries about it; sampling, which processes each item with probability \( \alpha \) and ignores it with probability \( 1 - \alpha \), is an alternative.[1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/)
**AMS sketch.** The frequency-moment problem asks for \( F_{p} = \sum_{i} |f_{i}|^{p} \), where \( f_{i} \) counts occurrences of universe element \( i \). The AMS sketch computes \( S \cdot f \) throughout the stream, where \( S \in \mathbb{R}^{t \times n} \) is a matrix of uniform \( \{ t^{-1/2}, -t^{-1/2} \} \) random variables; equivalently, it initializes a random sign vector \( s \) and outputs \( \langle s, f \rangle^{2} \), an unbiased estimator of \( F_{2} \), which repeated copies then aggregate into the \( (1 \pm \epsilon) \)-approximation of \( F_{2} \).[20](https://docs.rs/oxicuda-sketch/latest/oxicuda_sketch/moment/ams_f2/index.html) • [11](https://arxiv.org/pdf/2003.14265v3.pdf) The hash functions \( \sigma_{i}: [n] \to \{-1, 1\} \) are drawn from a 4-wise independent family, each representable in \( O(\log n) \) bits.[12](https://people.eecs.berkeley.edu/~minilek/tum2016/notes3.pdf) The estimator has high variance, so several independent copies are averaged and medians of averages are taken to drive the failure probability down.[1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/) The result is a \( (1 \pm \epsilon) \)-approximation of \( F_{2} \) with probability \( 1 - \delta \) using \( O((1/\epsilon^{2})\log(1/\delta)\log n) \) bits for a universe of size \( n \).[4](https://arxiv.org/pdf/2609.17286)
**Count-Min and CountSketch.** The Count-Min sketch, introduced by Graham Cormode and S. Muthukrishnan in 2004 in the Journal of Algorithms, is a fixed array of counters of width \( w \) and depth \( d \), each row with a pairwise hash function; with \( w \ge \lceil e/\epsilon \rceil \) and \( d \ge \lceil \ln(1/\delta) \rceil \) its point query is accurate with probability \( 1 - \delta \) at any time for nonnegative updates, as in the counting setting where all update values are \( +1 \).[21](https://ar5iv.labs.arxiv.org/html/2302.05245) • [13](https://doi.org/10.1016/j.jalgor.2003.12.001) • [1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/) CountSketch also supports positive and negative weight updates and uses memory \( O(1/\epsilon^{2}) \).[1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/)
**HyperLogLog.** [HyperLogLog](https://www.edgepedia.org/hyperloglog) performs a single pass and estimates cardinality with relative standard error about \( 1.04/\sqrt{m} \) using \( m \) registers; with \( m = 2048 \), 32-bit hashing, and 5-bit registers, cardinalities beyond \( 10^{9} \) are estimated with about 2% accuracy using 1.5 kB of storage.[6](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)
## Origin
The formal study of streaming computation was introduced by [Noga Alon](https://www.edgepedia.org/noga-alon) and colleagues in their 1996 paper "The space complexity of approximating the frequency moments", which showed almost tight upper and lower bounds for one-pass estimation.[5](https://www.ccs.neu.edu/home/viola/papers/BVWY-stream.pdf) • [14](https://mirrors.meulie.net/bitsavers.org/pdf/dec/tech_reports/SRC-TN-1998-011.pdf) A model of data streams was introduced for studying the space requirements of algorithms making one or a few passes over the input, and connected the setting to communication complexity.[14](https://mirrors.meulie.net/bitsavers.org/pdf/dec/tech_reports/SRC-TN-1998-011.pdf) An earlier precursor is work on selecting the \( k \)th largest of \( n \) elements in at most \( P \) passes, with an upper bound of \( n^{1/P} \log n \) and an almost matching lower bound of \( n^{1/P} \) for large enough \( k \).[14](https://mirrors.meulie.net/bitsavers.org/pdf/dec/tech_reports/SRC-TN-1998-011.pdf) The first algorithm for approximating \( F_{0} \), the number of distinct elements, is commonly named the AMS algorithm and is based on trailing zeros in binary representations of hashed items.[3](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes3.pdf)
## Variants
Space complexity depends sharply on the moment index \( p \). For \( 0 \le p \le 2 \), \( \mathrm{poly}(\epsilon^{-1} \log n) \) words of space is achievable; for \( p > 2 \) and constant \( \epsilon \), the space complexity is \( n^{1-2/p} \) up to logarithmic factors.[12](https://people.eecs.berkeley.edu/~minilek/tum2016/notes3.pdf) For \( p \le 2 \), \( F_{p} \) can be approximated using \( O(\epsilon^{-2}(\log t + \log m)\ln(1/\delta)) \) bits; for \( F_{\infty} \), the maximum frequency, linear memory in the stream length is required.[1](https://book.moa.cms.waikato.ac.nz/chapter_4.html/) In the turnstile model, \( \Theta(\epsilon^{-2}\log(mn)) \) bits is necessary and sufficient for a randomized one-pass \( (1 \pm \epsilon) \)-approximation to \( F_{p} \) for \( 0 < p \le 2 \), and using \( p \)-stable distributions, \( F_{p} \) for \( 0 < p < 2 \) can be approximated with \( O(\epsilon^{-2}\log n) \) bits, optimal up to a constant factor.[5](https://www.ccs.neu.edu/home/viola/papers/BVWY-stream.pdf)
## Applications
The core problems are frequency moments and their relatives: \( F_{0} \) equals the number of distinct items in the stream, \( F_{2} \) measures variance and estimates self-join size in database applications, and \( F_{p} \) for non-integer \( p \) measures entropy or skewness useful for query optimization.[5](https://www.ccs.neu.edu/home/viola/papers/BVWY-stream.pdf) Finding the most frequently occurring items in a stream is one of the most basic problems on data streams, under the assumption that the stream is too large for memory-intensive solutions such as sorting.[15](https://www.cs.helsinki.fi/u/jilu/paper/CountSketch.pdf) The Count-Min sketch supports point queries, dot products, \( L_{1} \) and \( L_{2} \) norm estimates, distinct-item counts, join and self-join sizes, and item and range sum queries.[13](https://doi.org/10.1016/j.jalgor.2003.12.001) The model also describes stream-processing systems: a data stream is a dataset produced incrementally over time, possibly unbounded, so systems cannot store the entire stream and must process elements on the fly with limited memory.[16](https://link.springer.com/article/10.1007/s00778-023-00819-8)
## Limitations and alternatives
**Lower bounds.** Henzinger, Raghavan, and Rajagopalan provided space lower bounds for concrete problems in the data stream model, derived from results in communication complexity.[8](https://dl.acm.org/doi/10.1145/543613.543615) For \( F_{2} \), the best known lower bound until 2025 was \( \Omega(1/\epsilon^{2} + \log n) \) due to Woodruff; Braverman and Zamir then proved a tight \( \Omega((1/\epsilon^{2})\log(n\epsilon^{2})) \) bound for constant failure probability in the insertion-only model.[4](https://arxiv.org/pdf/2609.17286) Exactly computing \( F_{2} \) requires storing all frequency counts, \( \Omega(n) \) space, which is what motivates sketching.[4](https://arxiv.org/pdf/2609.17286) For the median of a stream of length \( m \), \( \Omega(\log \log m) \) passes are needed for polylogarithmic space, and with two passes the space lower bound is \( \Omega(m^{1/10}) \).[17](https://theoryofcomputing.org/articles/v012a010/v012a010.pdf)
**Adversarial ordering.** Standard sketches are analyzed against oblivious streams, but an adversarially robust algorithm must keep its guarantees when the stream is chosen adaptively by an adversary observing the algorithm's outputs online.[11](https://arxiv.org/pdf/2003.14265v3.pdf) The AMS sketch is not adversarially robust even against an insertion-only adaptive adversary: an adversary can fool it into outputting a value that is not a \( (1 \pm \epsilon) \) estimate of \( F_{2} \).[11](https://arxiv.org/pdf/2003.14265v3.pdf) Robustness can be bought with space: any tracking algorithm using \( \mathrm{Space}(A) \) can be transformed into an adversarially robust one using at most \( \lambda_{\epsilon}(f) \cdot \mathrm{Space}(A) \), where \( \lambda_{\epsilon}(f) \) is the \( \epsilon \)-flip number.[18](http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/teaching/15859-fall21/lec19.pdf) Robust \( (1+\epsilon) \)-[approximation algorithms](https://www.edgepedia.org/approximation-algorithm) are known for distinct elements, \( F_{p} \) moments, heavy hitters, and entropy estimation in the insertion-only model, with space matching the best non-robust algorithms up to a \( \mathrm{poly}(\log n, 1/\epsilon) \) factor.[11](https://arxiv.org/pdf/2003.14265v3.pdf)
**Separations.** Adversarial robustness can cost asymptotically more space: there is a streaming problem over a domain of size \( \mathrm{poly}(w) \) and stream length \( O(w^{5}) \) that requires at least \( w \) space in the adversarial setting to constant accuracy but only \( O(\log^{2}(w)) \) space in the oblivious setting.[19](https://link.springer.com/chapter/10.1007/978-3-030-84252-9_4)
## References
1. [Machine Learning for Data Streams (Chapter 4)](https://book.moa.cms.waikato.ac.nz/chapter_4.html/)
2. [Weeks 4-5: Streaming and Parallel Algorithms (CSC473 lecture notes)](https://www.cs.toronto.edu/~anikolov/CSC473W20/Lectures/streaming.pdf)
3. [Streaming Algorithms (MPI-INF lecture notes, SS14)](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes3.pdf)
4. [High Probability Streaming Lower Bounds for F_2 Estimation](https://arxiv.org/pdf/2609.17286)
5. [Revisiting Frequency Moment Estimation in Random-Order Streams](https://www.ccs.neu.edu/home/viola/papers/BVWY-stream.pdf)
6. [HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)
7. [The Data Streaming Model (CMU 15-750 notes)](https://www.cs.cmu.edu/~15750/notes/streaming.pdf)
8. [Models and issues in data stream systems (PODS 2003)](https://dl.acm.org/doi/10.1145/543613.543615)
9. [Streaming Communication Protocols](https://www.irif.fr/~magniez/PAPIERS/bkm-toct18.pdf)
10. [Separations and equivalences between turnstile streaming and linear sketching (STOC 2020)](https://dl.acm.org/doi/10.1145/3357713.3384278)
11. [A Framework for Adversarially Robust Streaming Algorithms](https://arxiv.org/pdf/2003.14265v3.pdf)
12. [Sketching and streaming, Notes 3](https://people.eecs.berkeley.edu/~minilek/tum2016/notes3.pdf)
13. [Graham Cormode, S. Muthukrishnan (2004). An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms.](https://doi.org/10.1016/j.jalgor.2003.12.001)
14. [Computing on Data Streams (DEC SRC Technical Note 1998-011)](https://mirrors.meulie.net/bitsavers.org/pdf/dec/tech_reports/SRC-TN-1998-011.pdf)
15. [Finding Frequent Items in Data Streams](https://www.cs.helsinki.fi/u/jilu/paper/CountSketch.pdf)
16. [A survey on the evolution of stream processing systems (The VLDB Journal)](https://link.springer.com/article/10.1007/s00778-023-00819-8)
17. [Robust Lower Bounds for Communication and Stream Computation](https://theoryofcomputing.org/articles/v012a010/v012a010.pdf)
18. [CMU 15-859 Lecture 19: Adversarially Robust Streaming](http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/teaching/15859-fall21/lec19.pdf)
19. [Separating Adaptive Streaming from Oblivious Streaming Using the Bounded Storage Model (RANDOM/APPROX 2021)](https://link.springer.com/chapter/10.1007/978-3-030-84252-9_4)
20. [Index (docs.rs)](https://docs.rs/oxicuda-sketch/latest/oxicuda_sketch/moment/ams_f2/index.html)
21. [ar5iv.labs.arxiv.org](https://ar5iv.labs.arxiv.org/html/2302.05245)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures*
*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license