{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T11:13:20Z","timestamp":1784373200389,"version":"3.55.0"},"reference-count":219,"publisher":"Emerald","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,5,15]]},"abstract":"<jats:p>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].<\/jats:p>","DOI":"10.1561\/0400000002","type":"journal-article","created":{"date-parts":[[2005,9,29]],"date-time":"2005-09-29T08:42:26Z","timestamp":1127983346000},"page":"117-236","source":"Crossref","is-referenced-by-count":594,"title":["Data Streams: Algorithms and Applications"],"prefix":"10.1108","volume":"1","author":[{"given":"S.","family":"Muthukrishnan","sequence":"first","affiliation":[{"name":"Rutgers University , New Brunswick, NJ,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2005,5,15]]},"reference":[{"key":"2026041408270699200_ref001"},{"key":"2026041408270699200_ref002"},{"key":"2026041408270699200_ref003"},{"key":"2026041408270699200_ref004","volume-title":"Lance Fortnow"},{"issue":"2","key":"2026041408270699200_ref005","doi-asserted-by":"crossref","first-page":"120139","DOI":"10.1007\/s00778-003-0095-z","article-title":"Aurora: A new model and architecture for data stream management","volume":"12","author":"Abadi","year":"2003","journal-title":"VLDB Journal"},{"key":"2026041408270699200_ref006","first-page":"181","article-title":"Self-tuning histograms: Building histograms without looking at data","volume-title":"Proc. ACM SIGMOD","author":"Aboulnaga","year":"1998"},{"key":"2026041408270699200_ref007","first-page":"611","article-title":"Fast computation of low rank approximation","volume-title":"Proc. ACM STOC","author":"Achlioptas","year":"2001"},{"key":"2026041408270699200_ref008","unstructured":"L.\n              Adamic\n            \n          , \u201cZipf,\u201d power-law, pareto - a ranking tutorial, http:\/\/www.hpl.hp.com\/research\/idl\/papers\/ranking\/, 2000."},{"key":"2026041408270699200_ref009","doi-asserted-by":"crossref","volume-title":"Geometric Approximation via Coresets","author":"Agarwal","DOI":"10.1017\/9781009701259.002"},{"key":"2026041408270699200_ref010","first-page":"40","volume-title":"Advances in Cryptology - Eurocrypt","author":"Aggarwal","year":"2004"},{"key":"2026041408270699200_ref011","first-page":"370","article-title":"Counting inversions in a data stream","volume-title":"Proc. ACM STOC","author":"Ajtai","year":"2002"},{"key":"2026041408270699200_ref012","article-title":"Estimating sums of arbitrary selections with few probes","volume-title":"Proc. ACM PODS","author":"Alon","year":"2005"},{"key":"2026041408270699200_ref013","first-page":"10","article-title":"Tracking join and self-join sizes in limited storage","volume-title":"Proc. ACM PODS","author":"Alon","year":"1999"},{"key":"2026041408270699200_ref014","first-page":"20","article-title":"The space complexity of approximating the frequency moments","volume-title":"Proc. ACM STOC","author":"Alon","year":"1996"},{"key":"2026041408270699200_ref015","article-title":"STREAM: The stanford stream data manager","volume-title":"Proc. ACM SIGMOD","author":"Arasu","year":"2003"},{"key":"2026041408270699200_ref016","first-page":"286","article-title":"Approximate Counts and Quantiles over Sliding Windows","volume-title":"Proc. ACM PODS","author":"Arasu","year":"2004"},{"key":"2026041408270699200_ref017","first-page":"1","article-title":"Models and issues in data stream systems","volume-title":"Proc. ACM PODS","author":"Babcock","year":"2002"},{"key":"2026041408270699200_ref018","first-page":"144","article-title":"Deterministic sampling and range counting in geometric data streams","volume-title":"Proc. ACM SOCG","author":"Bagchi","year":"2004"},{"key":"2026041408270699200_ref019","article-title":"A one-pass sequential Monte Carlo method for Bayesian analysis of massive datasets","volume-title":"Manuscript","author":"Balakrishnan","year":"2004"},{"key":"2026041408270699200_ref020","first-page":"929","article-title":"Load management and high availability in the Medusa distributed stream processing system","volume-title":"Proc. ACM SIGMOD","author":"Balazinska","year":"2004"},{"key":"2026041408270699200_ref021","first-page":"209","article-title":"Information statistics approach to data stream and communication complexity","volume-title":"Proc. IEEE FOCS","author":"Bar-yossef","year":"2002"},{"key":"2026041408270699200_ref022","first-page":"1","article-title":"Counting distinct elements in a data stream","volume-title":"Proc. RANDOM","author":"Bar-Yossef","year":"2000"},{"key":"2026041408270699200_ref023","first-page":"623","article-title":"Reductions in streaming algorithms, with an application to counting triangles in graphs","volume-title":"Proc. ACM-SIAM SODA","author":"Bar-Yossef","year":"2002"},{"key":"2026041408270699200_ref024","first-page":"186","article-title":"Inferring mixtures of markov chains","volume-title":"Proc. COLT","author":"Batu","year":"2004"},{"key":"2026041408270699200_ref025","volume-title":"Walsh functions and their applications","author":"Beauchamp","year":"1975"},{"key":"2026041408270699200_ref026","first-page":"269","article-title":"The power of a pebble: Exploring and mapping directed graphs","volume-title":"Proc. ACM STOC","author":"Bender","year":"1998"},{"key":"2026041408270699200_ref027","first-page":"374","article-title":"Space efficient finger search on degree-balanced search trees","volume-title":"Proc. ACM-SIAM SODA","author":"Blelloch","year":"2003"},{"key":"2026041408270699200_ref028","first-page":"327","article-title":"Min-wise independent permutations","volume-title":"Proc. ACM STOC","author":"Broder","year":"1998"},{"key":"2026041408270699200_ref029","volume-title":"Workshop on Massive Geometric Datasets","author":"Buriol","year":"2005"},{"key":"2026041408270699200_ref030","first-page":"840","article-title":"Improved range-summable random variable construction algorithms","volume-title":"Proc. ACM-SIAM SODA","author":"Calderbank","year":"2005"},{"key":"2026041408270699200_ref031","first-page":"107","article-title":"Near-optimal lower bounds on the multi-party communication complexity of set disjointness","volume-title":"IEEE Conference on Computational Complexity","author":"Chakrabarti","year":"2003"},{"issue":"354","key":"2026041408270699200_ref032","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1080\/01621459.1976.10480344","article-title":"A method for simulating stable random variables","volume":"71","author":"Chambers","year":"1976","journal-title":"Journal of the American Statistical Association"},{"key":"2026041408270699200_ref033","volume-title":"Workshop on New Horizons in Computing","author":"Chan","year":"2005"},{"key":"2026041408270699200_ref034","first-page":"180","article-title":"Multi-pass geometric algorithms","volume-title":"Proc. ACM SoCG","author":"Chan","year":"2005"},{"key":"2026041408270699200_ref035","first-page":"626","article-title":"Incremental clustering and dynamic information retrieval","volume-title":"Proc. ACM STOC","author":"Charikar","year":"1997"},{"key":"2026041408270699200_ref036","first-page":"693","article-title":"Finding frequent items in data streams","volume-title":"Proc. ICALP","author":"Charikar","year":"2002"},{"key":"2026041408270699200_ref037","first-page":"693","article-title":"Better streaming algorithms for clustering problems","volume-title":"Proc. ACM STOC","author":"Charikar","year":"2003"},{"key":"2026041408270699200_ref038","first-page":"436","article-title":"Random sampling for histogram construction: How much is enough?","volume-title":"Proc. SIGMOD","author":"Chaudhuri","year":"1998"},{"key":"2026041408270699200_ref039","first-page":"379","article-title":"NiagaraCQ: A scalable continuous query system for internet databases","volume-title":"Proc. ACM SIGMOD","author":"Chen","year":"2000"},{"key":"2026041408270699200_ref040","unstructured":"S.\n              Chen\n            , A.Gaur, S.Muthukrishnan, and D.Rosenbluth, \u201cWireless in loco sensor data collection and applications,\u201d Workshop on Mobile Data Access (MOBEA) II, Held with WWW Conf, 2004."},{"key":"2026041408270699200_ref041","first-page":"222","article-title":"Clifford algebras and approximating the permanent","volume-title":"Proc. ACM STOC","author":"Chien","year":"2002"},{"key":"2026041408270699200_ref042","first-page":"707","article-title":"Spatially-decaying aggregation over a network: Model and algorithms","volume-title":"Proc. ACM SIGMOD","author":"Cohen","year":"2004"},{"key":"2026041408270699200_ref043","volume-title":"Technical Report TR1995-701","author":"Cole","year":"1995"},{"key":"2026041408270699200_ref044","first-page":"206","article-title":"Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms","volume-title":"Proc. ACM STOC","author":"Cole","year":"1986"},{"key":"2026041408270699200_ref045","first-page":"151","article-title":"An improved data stream algorithm for frequency moments","volume-title":"Proc. ACM-SIAM SODA","author":"Coppersmith","year":"2004"},{"key":"2026041408270699200_ref046","article-title":"Stable distributions for stream computations: It\u2019s as easy as 0,1,2","volume-title":"Workshop on Management and Processing of Massive Data Streams (MPDS) at FCRC","author":"Cormode","year":"2003"},{"key":"2026041408270699200_ref047","first-page":"335","article-title":"Comparing data streams using hamming norms (How to zero in)","volume-title":"Proc. VLDB","author":"Cormode","year":"2002"},{"key":"2026041408270699200_ref048","first-page":"13","article-title":"Sketching streams through the net: Distributed approximate query tracking","volume-title":"Proc. VLDB","author":"Cormode","year":"2005"},{"key":"2026041408270699200_ref049","first-page":"25","article-title":"Holistic aggregates in a networked world: Distributed tracking of approximate quantiles","volume-title":"Proc. ACM SIGMOD","author":"Cormode","year":"2005"},{"key":"2026041408270699200_ref050","first-page":"35","article-title":"Holistic UDAFs at streaming speeds","volume-title":"Proc. ACM SIGMOD","author":"Cormode","year":"2004"},{"key":"2026041408270699200_ref051","first-page":"464","article-title":"Finding hierarchical heavy hitters in data streams","volume-title":"Proc. VLDB","author":"Cormode","year":"2003"},{"key":"2026041408270699200_ref052","first-page":"155","article-title":"Diamond in the rough: Finding hierarchical heavy hitters in multi-dimensional data","volume-title":"Proc. ACM SIGMOD","author":"Cormode","year":"2004"},{"key":"2026041408270699200_ref053","first-page":"667","article-title":"The string edit distance matching problem with moves","volume-title":"Proc. ACM-SIAM SODA","author":"Cormode","year":"2002"},{"key":"2026041408270699200_ref054","first-page":"148","article-title":"Estimating dominance norms on multiple data streams","volume-title":"Proc. ESA","author":"Cormode","year":"2003"},{"key":"2026041408270699200_ref055","first-page":"296","article-title":"What is hot and what is not: Tracking most frequent items dynamically","volume-title":"Proc. ACM PODS","author":"Cormode","year":"2003"},{"key":"2026041408270699200_ref056","article-title":"Radial histograms for spatial streams","volume-title":"DIMACS Technical Report","author":"Cormode","year":"2003"},{"key":"2026041408270699200_ref057","article-title":"What is new: Finding significant differences in network data streams","volume-title":"Proc. INFOCOM","author":"Cormode","year":"2004"},{"key":"2026041408270699200_ref058","doi-asserted-by":"crossref","DOI":"10.1145\/1065167.1065201","article-title":"Space efficient mining of multigraph streams","volume-title":"Proc. ACM PODS","author":"Cormode","year":"2005"},{"key":"2026041408270699200_ref059","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611972757.5","article-title":"Summarizing and mining skewed data streams","volume-title":"Proc. SIAM SDM","author":"Cormode","year":"2005"},{"issue":"1","key":"2026041408270699200_ref060","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","article-title":"An improved data stream summary: The count-min sketch and its applications","volume":"55","author":"Cormode","year":"2005","journal-title":"J. Algorithms"},{"key":"2026041408270699200_ref061","first-page":"25","article-title":"Summarizing and mining inverse distributions on data streams via dynamic inverse sampling","volume-title":"Proc. VLDB","author":"Cormode","year":"2005"},{"key":"2026041408270699200_ref062","first-page":"481","article-title":"Permutation editing and matching via embeddings","volume-title":"Proc. ICALP","author":"Cormode","year":"2001"},{"key":"2026041408270699200_ref063","first-page":"197","article-title":"Communication complexity of document exchange","volume-title":"Proc. ACM-SIAM SODA","author":"Cormode","year":"2000"},{"key":"2026041408270699200_ref064","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1145\/347090.347094","article-title":"Hancock: A language for extracting signatures from data streams","volume-title":"Proc. KDD","author":"Cortes","year":"2000"},{"issue":"3","key":"2026041408270699200_ref065","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1023\/A:1011464915332","article-title":"Signature-based methods for data streams","volume":"5","author":"Cortes","year":"2001","journal-title":"Data Mining and Knowledge Discovery"},{"key":"2026041408270699200_ref066","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-44816-0_11","article-title":"Communities of interest","volume-title":"Proc. of Intelligent Data Analysis","author":"Cortes","year":"2001"},{"issue":"1","key":"2026041408270699200_ref067","first-page":"2732","article-title":"The gigascope stream database","volume":"26","author":"Cranor","year":"2003","journal-title":"IEEE Data Engineering Bulletin"},{"key":"2026041408270699200_ref068","doi-asserted-by":"crossref","DOI":"10.1002\/0471448354","volume-title":"Exploratory Data Mining and Data Quality","author":"Dasu","year":"2003"},{"key":"2026041408270699200_ref069","first-page":"240","article-title":"Mining database structure or how to build a data quality browser","volume-title":"Proc. ACM SIG MOD","author":"Dasu","year":"2002"},{"key":"2026041408270699200_ref070","first-page":"635","article-title":"Maintaining stream statistics over sliding windows","volume-title":"Proc. ACM-SIAM SODA","author":"Datar","year":"2002"},{"key":"2026041408270699200_ref071","first-page":"323","article-title":"Estimating rarity and similarity in window streams","volume-title":"Proc. ESA","author":"Datar","year":"2002"},{"key":"2026041408270699200_ref072","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF02678430","article-title":"Greedy adaptive approximation","volume":"13","author":"Davis","year":"1997","journal-title":"Journal of Constructive Approximation"},{"key":"2026041408270699200_ref073","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02888-9","volume-title":"Constructive Approximation","author":"DeVore","year":"1993"},{"key":"2026041408270699200_ref074","unstructured":"D.\n              Donoho\n            \n          , \u201cHigh-dimensional data analysis: The curses and blessings of dimensionality,\u201d Manuscript, 2000. http:\/\/www-stat.stanford.edu\/~donoho\/."},{"key":"2026041408270699200_ref075","unstructured":"D.\n              Donoho\n            \n          , \u201cCompressed sensing,\u201d Manuscript, 2004. http:\/\/www-stat.stanford.edu\/~donoho\/Reports\/2004\/CompressedSensing091604.pdf."},{"key":"2026041408270699200_ref076","first-page":"223","article-title":"Pass efficient algorithms for approximating large matrices","volume-title":"Proc. ACM-SIAM SODA","author":"Drineas","year":"2003"},{"key":"2026041408270699200_ref077","article-title":"Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication","volume-title":"Yale Technical Report","author":"Drineas","year":"2004"},{"key":"2026041408270699200_ref078","article-title":"Fast Monte Carlo algorithms for matrices II: Computing low-rank approximations to a matrix","volume-title":"Yale Technical Report","author":"Drineas","year":"2004"},{"key":"2026041408270699200_ref079","article-title":"Fast Monte Carlo algorithms for matrices III: Computing an efficient approximate decomposition of a matrix","volume-title":"Yale Technical Report","author":"Drineas","year":"2004"},{"key":"2026041408270699200_ref080","volume-title":"Combinatorial Group Testing and Its Applications","author":"Du","year":"2000","edition":"2nd"},{"key":"2026041408270699200_ref081","first-page":"85","article-title":"Flow sampling under hard resource constraints","volume-title":"Sigmetrics","author":"Duffield","year":"2004"},{"key":"2026041408270699200_ref082","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1145\/1011767.1011791","article-title":"Efficient algorithms for constructing (1 + \u03b5,\u03b2)- spanners in the distributed and streaming models","volume-title":"Proc. ACM PODC","author":"Elkin","year":"2004"},{"key":"2026041408270699200_ref083","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/863955.863972","article-title":"Automatically inferring patterns of resource consumption in network traffic","volume-title":"Proc. SIGCOMM","author":"Estan","year":"2003"},{"issue":"3","key":"2026041408270699200_ref084","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1145\/859716.859719","article-title":"New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice","volume":"21","author":"Estan","year":"2003","journal-title":"ACM Transactions on Computer System"},{"issue":"5","key":"2026041408270699200_ref085","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/229459.229469","article-title":"Comparing information without leaking it: Simple solutions","volume":"39","author":"Fagin","year":"1996","journal-title":"Communications of the ACM"},{"issue":"4","key":"2026041408270699200_ref086","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","article-title":"A threshold of ln n for approximating set cover","volume":"45","author":"Feige","year":"1998","journal-title":"Journal of ACM"},{"key":"2026041408270699200_ref087","volume-title":"Invited Lecture","author":"Feigenbaum","year":"1999"},{"key":"2026041408270699200_ref088","first-page":"927","article-title":"Secure multiparty computation of approximations","volume-title":"Proc. ICALP","author":"Feigenbaum","year":"2001"},{"key":"2026041408270699200_ref089","first-page":"531","article-title":"On graph problems in a semi-streaming model","volume-title":"Proc of ICALP","author":"Feigenbaum","year":"2004"},{"key":"2026041408270699200_ref090","first-page":"745","article-title":"Graph distances in the streaming model: The value of space","volume-title":"Proc. ACM-SIAM SODA","author":"Feigenbaum","year":"2005"},{"key":"2026041408270699200_ref091","first-page":"501","article-title":"An approximate L1 difference algorithm for massive data streams","volume-title":"Proc. IEEE FOCS","author":"Feigenbaum","year":"1999"},{"issue":"1","key":"2026041408270699200_ref092","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s00453-004-1105-2","article-title":"Computing diameter in the streaming and sliding window models","volume":"41","author":"Feigenbaum","year":"2004","journal-title":"Algorithmica"},{"key":"2026041408270699200_ref093","first-page":"376","article-title":"Finding a majority among N votes: Solution to problem 81-5","volume":"3","author":"Fischer","year":"1982","journal-title":"J. Algorithms"},{"key":"2026041408270699200_ref094","first-page":"76","article-title":"Probabilistic counting","volume-title":"Proc. FOCS","author":"Flajolet","year":"1983"},{"key":"2026041408270699200_ref095","first-page":"142","article-title":"Sampling in dynamic data streams and applications","volume-title":"Proc. ACM SoCG","author":"Frahling","year":"2005"},{"key":"2026041408270699200_ref096","first-page":"209","article-title":"Coresets in dynamic geometric data streams","volume-title":"Proc. ACM STOC","author":"Frahling","year":"2005"},{"key":"2026041408270699200_ref097","first-page":"1","volume-title":"Advances in Cryptology - Eurocrypt","author":"Freedman","year":"2004"},{"issue":"4","key":"2026041408270699200_ref098","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/s00778-004-0135-3","article-title":"Tracking set-expression cardinalities over continuous update streams","volume":"13","author":"Ganguly","year":"2004","journal-title":"VLDB Journal"},{"key":"2026041408270699200_ref099","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2026041408270699200_ref100","first-page":"166","article-title":"Deterministic wavelet thresholding for maximum-error metrics","volume-title":"Proc. ACM PODS","author":"Garofalakis","year":"2004"},{"key":"2026041408270699200_ref101","article-title":"Determinsitic algorithms for estimating heavy-hitters on Turnstile data streams","volume-title":"Manuscript","author":"Gasieniec","year":"2005"},{"key":"2026041408270699200_ref102","article-title":"Detecting malicious network traffic using inverse distributions of packet contents","volume-title":"Proc. MineNet, 2005, Held with Proc. ACM SIGCOMM","author":"Geiger","year":"2005"},{"key":"2026041408270699200_ref103","first-page":"281","article-title":"Estimating simple functions on the union of data streams","volume-title":"Proc. ACM SPAA","author":"Gibbons","year":"2001"},{"key":"2026041408270699200_ref104","first-page":"389","article-title":"Fast, small space algorithm for approximate histogram maintenance","volume-title":"Proc. ACM STOC","author":"Gilbert","year":"2002"},{"key":"2026041408270699200_ref105","first-page":"79","article-title":"Surfing wavelets on streams: One pass summaries for approximate aggregate queries","volume-title":"VLDB Journal","author":"Gilbert","year":"2001"},{"key":"2026041408270699200_ref106","article-title":"QuickSAND: Quick summary and analysis of network data","volume-title":"DIMACS Technical Report","author":"Gilbert","year":"2001"},{"key":"2026041408270699200_ref107","first-page":"454","article-title":"How to summarize the universe: Dynamic maintenance of quantiles","volume-title":"Proc. VLDB","author":"Gilbert","year":"2002"},{"key":"2026041408270699200_ref108","first-page":"243","article-title":"Approximation of functions over redundant dictionaries using coherence","volume-title":"Proc. ACM-SIAM SODA","author":"Gilbert","year":"2003"},{"key":"2026041408270699200_ref109","doi-asserted-by":"crossref","DOI":"10.1117\/12.615931","article-title":"Improved time bounds for near-optimal sparse Fourier representations","volume-title":"SPIE Conf","author":"Gilbert","year":"2005"},{"key":"2026041408270699200_ref110","first-page":"37","article-title":"Improved sparse approximation over quasi-coherent dictionaries","volume-title":"Intl Conf on Image Processing (ICIP)","author":"Gilbert","year":"2003"},{"key":"2026041408270699200_ref111","first-page":"173","article-title":"Identifying frequent items in sliding windows over on-line packet streams","volume-title":"Internet Measurement Conference","author":"Golab","year":"2003"},{"key":"2026041408270699200_ref112","unstructured":"O.\n              Goldreich\n            \n          , \u201cSecure multiparty computation,\u201d Book at http:\/\/philby.ucsd.edu\/cryptolib\/BOOKS\/oded-sc.html, 1998."},{"issue":"16","key":"2026041408270699200_ref113","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1093\/biomet\/40.3-4.237","article-title":"The population frequencies of species and the estimation of population parameters","volume":"40","author":"Good","year":"1953","journal-title":"Biometrika"},{"key":"2026041408270699200_ref114","unstructured":"J.\n              Gray\n             and T.Hey, \u201cIn search of petabyte databases,\u201d http:\/\/www.reseg.rch.microsoft.com\/Gray\/talks\/."},{"key":"2026041408270699200_ref115","first-page":"243","article-title":"Quickly generating billion-record synthetic databases","volume-title":"Proc. ACM SIGMOD","author":"Gray","year":"1994"},{"key":"2026041408270699200_ref116","doi-asserted-by":"crossref","DOI":"10.1145\/375663.375670","article-title":"Space-efficient online computation of quantile summaries","volume-title":"Proc. ACM SIGMOD","author":"Greenwald","year":"2001"},{"key":"2026041408270699200_ref117","article-title":"Space efficiency in synopsis construction algorithms","volume-title":"Proc. VLDB","author":"Guha","year":"2005"},{"key":"2026041408270699200_ref118","article-title":"Waveletssynopsis for data streams: Minimizing non- euclidean error","volume-title":"Proc. ACM KDD","author":"Guha","year":"2005"},{"key":"2026041408270699200_ref119","first-page":"681","article-title":"Histogramming data streams with fast per-item processing","volume-title":"Proc. ICALP","author":"Guha","year":"2002"},{"key":"2026041408270699200_ref120","doi-asserted-by":"crossref","DOI":"10.1145\/1132863.1132873","article-title":"Approximation and streaming algorithms for histogram construction problems","volume-title":"Journal version","author":"Guha"},{"key":"2026041408270699200_ref121","first-page":"471","article-title":"Data streams and histograms","volume-title":"Proc. ACM STOC","author":"Guha","year":"2001"},{"key":"2026041408270699200_ref122","first-page":"359","article-title":"Clustering data streams","volume-title":"Proc. IEEE FOCS","author":"Guha","year":"2000"},{"key":"2026041408270699200_ref123","doi-asserted-by":"crossref","DOI":"10.1145\/641480.641513","article-title":"Application of the two-sided depth test to CSG rendering","volume-title":"Proc. I3d, ACM Interactive 3D graphics","author":"Guha","year":"2003"},{"key":"2026041408270699200_ref124","first-page":"253","article-title":"Counting inversions in lists","volume-title":"ACM-SIAM SODA","author":"Gupta","year":"2003"},{"key":"2026041408270699200_ref125","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01456326","article-title":"Zur theorie der orthogonalen functionsysteme","volume":"69","author":"Haar","year":"1910","journal-title":"Math Annal."},{"key":"2026041408270699200_ref126","article-title":"Slogging","volume-title":"Keynote plenary talk at SIAM Conf. Data Mining","author":"Hansen","year":"2005"},{"key":"2026041408270699200_ref127","volume-title":"Technical Note 1998-011","author":"Henzinger","year":"1998"},{"key":"2026041408270699200_ref128","doi-asserted-by":"crossref","DOI":"10.1145\/1065167.1065211","article-title":"Space complexity of hierarchical heavy hitters in multi-dimensional data streams","volume-title":"Proc. ACM PODS","author":"Hershberger","year":"2005"},{"key":"2026041408270699200_ref129","first-page":"252","article-title":"Adaptive sampling for geometric problems over data streams","volume-title":"Proc. ACM PODS","author":"Hershberger","year":"2004"},{"issue":"6","key":"2026041408270699200_ref130","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","article-title":"A linear space algorithm for computing maximal common subsequences","volume":"18","author":"Hirschberg","year":"1975","journal-title":"Comm. ACM"},{"key":"2026041408270699200_ref131","article-title":"Location streams: Models and Algorithms","volume-title":"DIMACS TR","author":"Hoffman","year":"2004"},{"key":"2026041408270699200_ref132","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1145\/566570.566639","article-title":"Chromium: A stream processing framework for interactive rendering on clusters","volume-title":"Proc. ACM SIGGRAPH","author":"Humphreys","year":"2002"},{"key":"2026041408270699200_ref133","doi-asserted-by":"crossref","volume-title":"Streaming Algorithms for Geometric Problems","author":"Indyk","DOI":"10.1007\/978-3-540-30538-5_3"},{"key":"2026041408270699200_ref134","first-page":"189","article-title":"Stable distributions, pseudorandom generators, embeddings and data stream computation","volume-title":"Proc. IEEE FOCS","author":"Indyk","year":"2000"},{"issue":"1","key":"2026041408270699200_ref135","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1006\/jagm.2000.1131","article-title":"A small approximately min-wise independent family of hash functions","volume":"38","author":"Indyk","year":"2001","journal-title":"Journal of Algorithms"},{"key":"2026041408270699200_ref136","first-page":"539","article-title":"Better algorithms for high dimensional proximity problems via asymmetric embeddings","volume-title":"Proc. ACM-SIAM SODA","author":"Indyk","year":"2003"},{"key":"2026041408270699200_ref137","article-title":"Stream-based geometric algorithms","volume-title":"Proc. ACM\/DIMACS Workshop on Management and Processing of Data Streams (MPDS)","author":"Indyk","year":"2003"},{"key":"2026041408270699200_ref138","first-page":"373","article-title":"Algorithms for dynamic geometric problems over data streams","volume-title":"Proc. ACM STOC","author":"Indyk","year":"2004"},{"key":"2026041408270699200_ref139","doi-asserted-by":"crossref","DOI":"10.1109\/SFCS.2003.1238202","article-title":"Tight lower bounds for the distinct elements problem","volume-title":"Proc. IEEE FOCS","author":"Indyk","year":"2003"},{"key":"2026041408270699200_ref140","first-page":"202","article-title":"Optimal approximations of the frequency moments of data streams","volume-title":"Proc. ACM STOC","author":"Indyk","year":"2005"},{"key":"2026041408270699200_ref141","doi-asserted-by":"crossref","DOI":"10.1145\/1081870.1081942","article-title":"Privacy-preserving distributed k-means clustering over arbitrarily partitioned data","volume-title":"Proc. ACM KDD","author":"Jagannathan","year":"2005"},{"key":"2026041408270699200_ref142","first-page":"1","article-title":"Sampling algorithms in a stream operator","volume-title":"Proc. ACM SIGMOD","author":"Johnson","year":"2005"},{"key":"2026041408270699200_ref143","first-page":"1","volume-title":"Proc.of 19th Annual IFIP Conference on Data and Applications Security","author":"Johnson","year":"2005"},{"key":"2026041408270699200_ref144","first-page":"96","article-title":"Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet","volume-title":"ASPLOS-X Conference","author":"Juang","year":"2002"},{"key":"2026041408270699200_ref145","volume-title":"Open problems in streaming","author":"Kannan"},{"key":"2026041408270699200_ref146","first-page":"51","article-title":"A simple algorithm for finding frequent elements in sets and bags","volume-title":"ACM Transactions on Database Systems","author":"Karp","year":"2003"},{"key":"2026041408270699200_ref147","first-page":"91","article-title":"Bursty and hierarchical structure in streams","volume-title":"Proc. ACM KDD","author":"Kleinberg","year":"2002"},{"key":"2026041408270699200_ref148","volume-title":"The art of computer programming, Volume III: Sorting and searching","author":"Knuth","year":"1973"},{"key":"2026041408270699200_ref149","first-page":"253","article-title":"Observed structure of addresses in IP traffic","volume-title":"Internet Measurement Workshop","author":"Kohler","year":"2002"},{"key":"2026041408270699200_ref150","first-page":"13","article-title":"On computing correlated aggregates over continual data streams","volume-title":"Proc. ACM SIGMOD","author":"Korn","year":"2001"},{"key":"2026041408270699200_ref151","first-page":"814","article-title":"Reverse nearest neighbor aggregates over data streams","volume-title":"Proc. VLDB","author":"Korn","year":"2002"},{"key":"2026041408270699200_ref152","article-title":"Model fitting of IP network traffic at streaming speeds","volume-title":"Manuscript","author":"Korn","year":"2005"},{"key":"2026041408270699200_ref153","first-page":"536","article-title":"Checks and balances: Monitoring data quality in network traffic databases","volume-title":"Proc. VLDB","author":"Korn","year":"2003"},{"key":"2026041408270699200_ref154","first-page":"234","article-title":"Sketch-based change detection: Methods, evaluation, and applications","volume-title":"Proc. ACM SIGCOMM Internet Measurement Conference","author":"Krishnamurthy","year":"2003"},{"issue":"1","key":"2026041408270699200_ref155","first-page":"11","article-title":"TelegraphCQ: An Architectural Status Report","volume":"26","author":"Krishnamurthy","year":"2003","journal-title":"IEEE Data Engineering Bulletin"},{"key":"2026041408270699200_ref156","volume-title":"Sublinear time algorithms","author":"Kumar","year":"2003"},{"key":"2026041408270699200_ref157","volume-title":"Communication Complexity","author":"Kushilevitz","year":"1997"},{"key":"2026041408270699200_ref158","article-title":"Counting solutions of polynomial equations","volume-title":"Manuscript","author":"Levchenko","year":"2005"},{"key":"2026041408270699200_ref159","first-page":"12","article-title":"On the difficulty of scalably detecting network attacks","volume-title":"ACM Conference on Computer and Communications Security","author":"Levchenko","year":"2004"},{"key":"2026041408270699200_ref160","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the hardness of approximating minimization problems","volume":"41","author":"Lund","year":"1994","journal-title":"Journal of ACM"},{"key":"2026041408270699200_ref161","first-page":"126","article-title":"Locating hidden groups in communication networks using hidden Markov models","volume-title":"Proc. ISI","author":"Magdon-Ismail","year":"2003"},{"key":"2026041408270699200_ref162","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/570738.570751","article-title":"Wireless sensor networks for habitat monitoring","volume-title":"Proc. WSNA","author":"Mainwaring","year":"2002"},{"key":"2026041408270699200_ref163","first-page":"767","article-title":"Finding (recently) frequent items in distributed data streams","volume-title":"Proc. ICDE","author":"Manjhi","year":"2005"},{"key":"2026041408270699200_ref164","first-page":"346","article-title":"Approximate frequency counts over data streams","volume-title":"Proc. VLDB","author":"Manku","year":"2002"},{"key":"2026041408270699200_ref165","first-page":"251","article-title":"Random sampling techniques for space efficient online computation of order statistics of large datasets","volume-title":"Proc. ACM SIGMOD","author":"Manku","year":"1999"},{"key":"2026041408270699200_ref166","article-title":"Interactive geometric computations using graphics hardware. Course","volume-title":"ACM SIGGRAPH","author":"Manocha","year":"2002"},{"key":"2026041408270699200_ref167","first-page":"368","article-title":"Optimal workload-based wavelet synopses","volume-title":"Proc. ICDT","author":"Matias","year":"2005"},{"key":"2026041408270699200_ref168","first-page":"398","article-title":"Efficient computation of frequent and top-k elements in data stream","volume-title":"Proc. ICDT","author":"Metwally","year":"2005"},{"key":"2026041408270699200_ref169","volume-title":"Technical Report","author":"Minsky","year":"2000-1796"},{"key":"2026041408270699200_ref170","first-page":"439","article-title":"Sublinear time approximate clustering","volume-title":"Proc. ACM-SIAM SODA","author":"Mishra","year":"2001"},{"key":"2026041408270699200_ref171","first-page":"143","article-title":"Finding repeated elements","volume-title":"Science of Computer Programming","author":"Misra","year":"1982"},{"key":"2026041408270699200_ref172","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"Motwani","year":"1995"},{"key":"2026041408270699200_ref173","volume-title":"Computational Geometry: An Introduction through Randomized Algorithms","author":"Mulmuley","year":"1993"},{"key":"2026041408270699200_ref174","first-page":"253","article-title":"Selection and sorting with limited storage","volume":"12","author":"Munro","year":"1978","journal-title":"Proc. IEEE FOCS"},{"key":"2026041408270699200_ref175","unstructured":"S.\n              Muthukrishnan\n            \n          , \u201cData streams: Algorithms and applications,\u201d http:\/\/www.cs.rutgers.edu\/~muthu\/stream-1-1.ps."},{"key":"2026041408270699200_ref176","article-title":"Nonuniform sparse approximation with Haar wavelet basis","volume-title":"DIMACS TR","author":"Muthukrishnan","year":"2004"},{"key":"2026041408270699200_ref177","first-page":"236","article-title":"On rectangular partitionings in two dimensions: Algorithms, complexity and applications","volume-title":"Proc. ICDT","author":"Muthukrishnan","year":"1999"},{"key":"2026041408270699200_ref178","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1145\/335305.335353","article-title":"Approximate nearest neighbors and sequence comparison with block operations","volume-title":"Proc. STOC","author":"Muthukrishnan","year":"2000"},{"key":"2026041408270699200_ref179","first-page":"41","article-title":"Finding deviants on data streams","volume-title":"Proc. SSDBM","author":"Muthukrishnan","year":"2004"},{"key":"2026041408270699200_ref180","article-title":"Approximate histogram and wavelet summaries of streaming data","volume-title":"DIMACS TR","author":"Muthukrishnan","year":"2004"},{"key":"2026041408270699200_ref181","first-page":"352","article-title":"Maintenance of multidimensional histograms","volume-title":"Proc. FSTTCS","author":"Muthukrishnan","year":"2003"},{"key":"2026041408270699200_ref182","first-page":"233","article-title":"Rangesum histograms","volume-title":"ACM-SIAM SODA","author":"Muthukrishnan","year":"2003"},{"key":"2026041408270699200_ref183","doi-asserted-by":"crossref","DOI":"10.1007\/11561071_65","article-title":"Workload-optimal histograms on streams","volume-title":"Proc. ESA","author":"Muthukrishnan","year":"2005"},{"issue":"2","key":"2026041408270699200_ref184","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/S0097539792240406","article-title":"Sparse approximate solutions to linear systems","volume":"25","author":"Natarajan","year":"1995","journal-title":"SIAM J. Computing"},{"key":"2026041408270699200_ref185","doi-asserted-by":"crossref","DOI":"10.1145\/1031495.1031525","article-title":"Synopsis diffusion for robust aggregation in sensor networks","volume-title":"Intel Tech Report, IRP-TR-04-13","author":"Nath","year":"2004"},{"key":"2026041408270699200_ref186","first-page":"179","article-title":"Always good turing: Asymptotically optimal probability estimation","volume-title":"Proc. IEEE FOCS","author":"Orlitsky","year":"2003"},{"key":"2026041408270699200_ref187","unstructured":"M.\n              Parseval\n            \n          \n          http:\/\/encyclopedia.thefreedictionary.com\/Parseval\u2019s+theorem1799."},{"key":"2026041408270699200_ref188","article-title":"Cryptographic techniques for privacy-preserving data mining","volume-title":"SIGKDD Explorations, the newsletter of the ACM Special Interest Group on Knowledge Discovery and Data Mining","author":"Pinkas","year":"2003"},{"key":"2026041408270699200_ref189","article-title":"A minimum storage algorithm for computing the median","volume-title":"IBM TR","author":"Pohl","year":"1969"},{"key":"2026041408270699200_ref190","first-page":"123","article-title":"Graph structure of the web: A survey","volume-title":"Proc. LATIN","author":"Raghavan","year":"2000"},{"key":"2026041408270699200_ref191","first-page":"739","article-title":"Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus","volume-title":"Proc. STOC","author":"Razborov","year":"1997"},{"key":"2026041408270699200_ref192","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1145\/1060590.1060647","article-title":"Undirected ST-connectivity in logspace","volume-title":"Proc. STOC","author":"Reingold","year":"2005"},{"key":"2026041408270699200_ref193","first-page":"300","article-title":"Symmetry breaking for suffix tree construction","volume-title":"Proc. of 26th Symposium on Theory of Computing","author":"Sahinalp","year":"1994"},{"key":"2026041408270699200_ref194","volume-title":"Technical Report","author":"Sahinalp","year":"1995"},{"key":"2026041408270699200_ref195","first-page":"320","article-title":"Efficient approximate and dynamic matching of patterns using a labeling paradigm","volume-title":"Proc. IEEE FOCS","author":"Sahinalp","year":"1996"},{"key":"2026041408270699200_ref196","first-page":"360","article-title":"Space lower bounds for distance approximation in the data stream model","volume-title":"Proc. ACM STOC","author":"Saks","year":"2002"},{"key":"2026041408270699200_ref197","first-page":"585","article-title":"Query processing in tertiary memory databases","volume-title":"Proc. VLDB","author":"Sarawagi","year":"1995"},{"key":"2026041408270699200_ref198","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/BF01940876","article-title":"Randomized search trees","volume":"16","author":"Seidel","year":"1996","journal-title":"Algorithmica"},{"key":"2026041408270699200_ref199","first-page":"76","article-title":"Maintaining statistics counters in router line cards","volume-title":"IEEE Micro","author":"Shah","year":"2002"},{"key":"2026041408270699200_ref200","doi-asserted-by":"crossref","DOI":"10.1145\/1031495.1031524","article-title":"Medians and beyond: New aggregation techniques for sensor networks","volume-title":"Proc. ACM SenSys","author":"Shrivastava","year":"2004"},{"issue":"1","key":"2026041408270699200_ref201","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1017\/S0963548300000080","article-title":"Three thresholds for a liar","volume":"1","author":"Spencer","year":"1992","journal-title":"Combinatorics, Probability and Computing"},{"key":"2026041408270699200_ref202","volume-title":"Proc. of the Workshop on Secure Data Management","author":"Subramaniam","year":"2004"},{"key":"2026041408270699200_ref203","first-page":"160","article-title":"Range counting over multidimensional data streams","volume-title":"Proc. ACM SoCG","author":"Suri","year":"2004"},{"key":"2026041408270699200_ref204","article-title":"Naer optimality of the priority sampling procedure","volume-title":"ECCC TR05-001","author":"Szegedy","year":"2005"},{"key":"2026041408270699200_ref205","unstructured":"J.\n              Tarui\n            \n          \n          Finding duplicates in passes. Personal Communication and http:\/\/weblog.fortnow.com\/2005\/03\/finding-duplicates.html#comments."},{"key":"2026041408270699200_ref206","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1023\/A:1018900431309","article-title":"The best m-term approximation and greedy algorithms","volume":"8","author":"Temlyakov","year":"1998","journal-title":"Advances in Computational Math."},{"key":"2026041408270699200_ref207","first-page":"428","article-title":"Dynamic multidimensional histograms","volume-title":"Proc. ACM SIGMOD","author":"Thaper","year":"2002"},{"issue":"10","key":"2026041408270699200_ref208","doi-asserted-by":"crossref","first-page":"2231","DOI":"10.1109\/TIT.2004.834793","article-title":"Greed is good: Algorithmic results for sparse approximation","volume":"50","author":"Tropp","year":"2004","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2026041408270699200_ref209","article-title":"Detecting packet patterns at high speeds","volume-title":"Tutorial at ACM SIGCOMM","author":"Varghese","year":"2002"},{"key":"2026041408270699200_ref210","article-title":"New streaming algorithms for superspreader detection","volume-title":"Network and Distributed Systems Security Symposium","author":"Venkataraman","year":"2005"},{"key":"2026041408270699200_ref211","unstructured":"S.\n              Venkatasubramanian\n            \n          , \u201cThe graphics card as a stream computer,\u201d Proc. ACM\/DIMACS Workshop on Management and Processing of Data Streams (MPDS), 2003, See also: http:\/\/www.research.att.com\/~suresh\/papers\/mpds\/index.html."},{"key":"2026041408270699200_ref212","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s003659900046","article-title":"Best approximation with walsh atoms","volume":"133","author":"Villemoes","year":"1997","journal-title":"Constructive Approximation"},{"issue":"2","key":"2026041408270699200_ref213","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","article-title":"External memory algorithms and data structures: Dealing with massive data","volume":"33","author":"Vitter","year":"2001","journal-title":"ACM Computing Surveys"},{"key":"2026041408270699200_ref214","volume-title":"Modern Computer Algebra","author":"von zur Gathen","year":"1999"},{"issue":"2","key":"2026041408270699200_ref215","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.ipl.2004.09.018","article-title":"Fast estimation of fractal dimension and correlation integral on stream data","volume":"93","author":"Wong","year":"2005","journal-title":"Inf. Process. Lett."},{"key":"2026041408270699200_ref216","first-page":"167","article-title":"Optimal space lower bounds for all frequency moments","volume-title":"Proc. ACM-SIAM SODA","author":"Woodruff","year":"2004"},{"key":"2026041408270699200_ref217","first-page":"160","article-title":"Protocols for secure computations","volume-title":"Proc. IEEE FOCS","author":"Yao","year":"1982"},{"key":"2026041408270699200_ref218","first-page":"101","article-title":"Online identification of hierarchical heavy hitters: Algorithms, evaluation, and applications","volume-title":"Proc. of the Internet Measurement Conference (IMC)","author":"Zhang","year":"2004"},{"key":"2026041408270699200_ref219","volume-title":"Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology","author":"Zipf","year":"1949"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/1\/2\/117\/11515201\/0400000002en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/1\/2\/117\/11515201\/0400000002en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:15Z","timestamp":1777489275000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/1\/2\/117\/1359601\/Data-Streams-Algorithms-and-Applications"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,15]]},"references-count":219,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,5,15]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000002","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5,15]]}}}