Finding Frequent Items in Data Streams

Summary: Unified framework and baseline implementations for comparing frequent-item stream algorithms, correcting fragmented prior evaluations. Extensive experiments reveal substantial performance variation: top methods achieve high accuracy with tens of KB memory at millions of items/sec. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9992
Venue: VLDB
Year: 2008
Pagerank: 0.00013419017
Overall Rank: 885 | 93.93%
DOI: 10.14778/1454159.1454238

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. Marios Hadjieleftheriou (AT&T)

BibTeX Citation

@article{cormode_vldb08,
        title = {{Finding Frequent Items in Data Streams}},
        author = {Cormode, Graham and Hadjieleftheriou, Marios},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {2},
        pages = {1530--1541},
        doi = {10.14778/1454159.1454238},
        url = {https://doi.org/10.14778/1454159.1454238},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
451	Mergeable Summaries	2012	PODS	0.00018151445
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010240222
1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	0.00010070362
1,905	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.5034849e-05
2,377	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.6710302e-05
2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	8.0058242e-05
3,445	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.4089141e-05
3,765	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.1442477e-05
3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	7.0856664e-05
3,856	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	7.0690791e-05
4,855	Structural Trend Analysis for Online Social Networks	2011	VLDB	6.4766126e-05
4,863	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.4740702e-05
4,898	Finding Persistent Items in Data Streams	2017	VLDB	6.454197e-05
5,522	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.1871697e-05
6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.949619e-05
6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.8746921e-05
7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.6021153e-05
7,807	Efficient Approximate Algorithms for Empirical Entropy and Mutual Information	2021	SIGMOD	5.5404259e-05
7,879	Authenticated Online Data Integration Services	2015	SIGMOD	5.5245691e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
8,231	Thread Cooperation in Multicore Architectures for Frequency Counting over Multiple Data Streams	2009	VLDB	5.4617036e-05
8,247	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.4574671e-05
9,329	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.2894515e-05
10,910	Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing	2025	VLDB	5.093636e-05
10,955	DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees	2025	VLDB	5.093636e-05
11,700	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	5.093636e-05
12,001	Runtime Optimization of Join Location in Parallel Data Management Systems	2017	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
2,808	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1006881e-05
2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.8907087e-05
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
4,005	Fast Data Stream Algorithms using Associative Memories	2007	SIGMOD	6.9643802e-05
4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.8764637e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,898	Finding Persistent Items in Data Streams	2017	VLDB
2	2,808	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS
3	8,603	Stream Frequency over Interval Queries	2019	VLDB
4	13,997	Mining Frequent Itemsets with Bit Strings and Trie	2002	VLDB
5	9,212	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS
6	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
7	6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
8	12,176	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD
9	4,683	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB
10	122	Approximate Frequency Counts over Data Streams	2002	VLDB