The DOI matches its Crossref record; 100 of the 100 references it cites were found in a registry or an index.
Data Streams: Algorithms and Applications
Abstract
In the data stream scenario, input arrives very rapidly and there is limited memory to store the input. Algorithms have to work with one or few passes over the data, space less than linear in the input size or time significantly less than the input size. In the past few years, a new theory has emerged for reasoning about algorithms that work within these constraints on space, time, and number of passes. Some of the methods rely on metric embeddings, pseudo-random computations, sparse approximation theory and communication complexity. The applications for this scenario include IP network traffic analysis, mining text message streams and processing massive data sets in general. Researchers in Theoretical Computer Science, Databases, IP Networking and Computer Systems are working on the data stream challenges. This article is an overview and survey of data stream algorithmics and is an updated version of [175].
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Donoho, D. L. (2004) · Cited by 16,703
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Wireless sensor networks for habitat monitoring
Mainwaring, A., Culler, D., Polastre, J., Szewczyk, R., & Anderson, J. (2002) · Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications · doi:10.1145/570738.570751 · Cited by 4,166
Greed is Good: Algorithmic Results for Sparse Approximation
Tropp, J. A. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834793 · Cited by 3,635
THE POPULATION FREQUENCIES OF SPECIES AND THE ESTIMATION OF POPULATION PARAMETERS
GOOD, I. J. (1953) · Biometrika · doi:10.1093/biomet/40.3-4.237 · Cited by 3,437
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
Sparse Approximate Solutions to Linear Systems
Natarajan, B. K. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792240406 · Cited by 2,783
Protocols for secure computations
Yao, A. C.-C. (1982) · doi:10.1109/sfcs.1982.88 · Cited by 2,661
Models and issues in data stream systems
Babcock, B., Babu, S., Datar, M., Motwani, R., & Widom, J. (2002) · Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/543613.543615 · Cited by 2,495
Cited by
Computational Methods for Sparse Solution of Linear Inverse Problems
Tropp, J. A., & Wright, S. J. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2044010 · Cited by 1,046
Signal Processing With Compressive Measurements
Davenport, M. A., Boufounos, P. T., Wakin, M. B., & Baraniuk, R. G. (2010) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2009.2039178 · Cited by 623
Beyond streams and graphs: dynamic tensor analysis
Sun, J., Tao, D., & Faloutsos, C. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150445 · Cited by 462
Dias de Assunção, M., da Silva Veith, A., & Buyya, R. (2018) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2017.12.001 · Cited by 304
Berthet-Rayne, P., Leibrandt, K., Gras, G., Fraisse, P., Crosnier, A., & Yang, G.-Z. (2018) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2018.2812907 · Cited by 58
Metadata
- Authors
- Muthukrishnan, S.
- Venue
- Foundations and Trends® in Theoretical Computer Science
- Publisher
- Emerald
- Published
- 2005
- Volume
- 1
- Issue
- 2
- Pages
- 117-236
- ISSN
- 1551-305X (ISSN-L)
- 1551-3068
- OpenAlex
- W1995484833
- Cited by
- 718
- References
- 100
- FWCI
- 32.89
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Data Streams: Algorithms and Applications. https://app.cochat.ai/papers/10.1561/0400000002
- The paper
- Muthukrishnan, S. (2005). Data Streams: Algorithms and Applications. Foundations and Trends® in Theoretical Computer Science. https://doi.org/10.1561/0400000002
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
