{ "id": "eprrqe0asj", "slug": "streaming-model-algorithms", "title": "Streaming model (algorithms)", "updated": "2026-09-30", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete" }, { "id": "physical.math.discrete.discrete", "label": "General discrete mathematics and discrete structures", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete" } ], "geo": [ { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Non-geographic · 1946 to 2000: Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical" }, { "id": "geo.nongeo.t1946.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math" }, { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete" } ] } ], "excerpt": "The streaming model is a computational model where input arrives as a sequential stream and an algorithm with small memory processes it in one or a few passes.", "snippet": "The streaming model is a computational model where input arrives as a sequential stream and an algorithm with small memory processes it in one or a few passes.", "node": "physical.math.discrete.discrete", "markdown": "# Streaming model (algorithms)\n\nThe 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)\n\n| Key fact | Value |\n|---|---|\n| 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/) |\n| Memory bound | \\( O(\\log^{c}(nm)) \\) bits for fixed \\( c \\)[2](https://www.cs.toronto.edu/~anikolov/CSC473W20/Lectures/streaming.pdf) |\n| 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) |\n| \\( F_{2} \\) estimation | \\( O((1/\\epsilon^{2})\\log(1/\\delta)\\log n) \\) bits via the AMS sketch[4](https://arxiv.org/pdf/2609.17286) |\n| 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) |\n| 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/) |\n| 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) |\n\n## How it works\n\nA 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)\n\nTwo 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)\n\n## How it is done\n\nA 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/)\n\n**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)\n\n**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/)\n\n**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)\n\n## Origin\n\nThe 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)\n\n## Variants\n\nSpace 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)\n\n## Applications\n\nThe 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)\n\n## Limitations and alternatives\n\n**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)\n\n**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)\n\n**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)\n\n## References\n\n1. [Machine Learning for Data Streams (Chapter 4)](https://book.moa.cms.waikato.ac.nz/chapter_4.html/)\n2. [Weeks 4-5: Streaming and Parallel Algorithms (CSC473 lecture notes)](https://www.cs.toronto.edu/~anikolov/CSC473W20/Lectures/streaming.pdf)\n3. [Streaming Algorithms (MPI-INF lecture notes, SS14)](https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss14/gitcs/notes3.pdf)\n4. [High Probability Streaming Lower Bounds for F_2 Estimation](https://arxiv.org/pdf/2609.17286)\n5. [Revisiting Frequency Moment Estimation in Random-Order Streams](https://www.ccs.neu.edu/home/viola/papers/BVWY-stream.pdf)\n6. [HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)\n7. [The Data Streaming Model (CMU 15-750 notes)](https://www.cs.cmu.edu/~15750/notes/streaming.pdf)\n8. [Models and issues in data stream systems (PODS 2003)](https://dl.acm.org/doi/10.1145/543613.543615)\n9. [Streaming Communication Protocols](https://www.irif.fr/~magniez/PAPIERS/bkm-toct18.pdf)\n10. [Separations and equivalences between turnstile streaming and linear sketching (STOC 2020)](https://dl.acm.org/doi/10.1145/3357713.3384278)\n11. [A Framework for Adversarially Robust Streaming Algorithms](https://arxiv.org/pdf/2003.14265v3.pdf)\n12. [Sketching and streaming, Notes 3](https://people.eecs.berkeley.edu/~minilek/tum2016/notes3.pdf)\n13. [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)\n14. [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)\n15. [Finding Frequent Items in Data Streams](https://www.cs.helsinki.fi/u/jilu/paper/CountSketch.pdf)\n16. [A survey on the evolution of stream processing systems (The VLDB Journal)](https://link.springer.com/article/10.1007/s00778-023-00819-8)\n17. [Robust Lower Bounds for Communication and Stream Computation](https://theoryofcomputing.org/articles/v012a010/v012a010.pdf)\n18. [CMU 15-859 Lecture 19: Adversarially Robust Streaming](http://www.cs.cmu.edu/afs/cs/user/dwoodruf/www/teaching/15859-fall21/lec19.pdf)\n19. [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)\n20. [Index (docs.rs)](https://docs.rs/oxicuda-sketch/latest/oxicuda_sketch/moment/ams_f2/index.html)\n21. [ar5iv.labs.arxiv.org](https://ar5iv.labs.arxiv.org/html/2302.05245)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [ "https://www.cs.toronto.edu/~anikolov/CSC473W20/Lectures/streaming.pdf", "https://www.cs.cmu.edu/~15750/notes/streaming.pdf", "https://people.eecs.berkeley.edu/~minilek/tum2016/notes3.pdf" ], "url": "https://www.edgepedia.org/streaming-model-algorithms", "markdown_url": "https://www.edgepedia.org/streaming-model-algorithms.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Streaming model (algorithms)\", Edgepedia (EdgeChat), https://www.edgepedia.org/streaming-model-algorithms. Edgepedia Community License 1.0.", "credit_md": "\"[Streaming model (algorithms)](https://www.edgepedia.org/streaming-model-algorithms)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/streaming-model-algorithms](https://www.edgepedia.org/streaming-model-algorithms). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Streaming model (algorithms)\", Edgepedia (EdgeChat), https://www.edgepedia.org/streaming-model-algorithms. Edgepedia Community License 1.0.", "speakable": "The streaming model is a computational model where input arrives as a sequential stream and an algorithm with small memory processes it in one or a few passes." }