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: h9b0ba73449fc8171
Venue: VLDB
Year: 2008
Pagerank: 0.00013125647
Overall Rank: 909 | 93.89%
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
456	Mergeable Summaries	2012	PODS	0.0001791284
1,319	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011045888
1,636	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010016656
1,678	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.9088372e-05
1,970	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.2902522e-05
2,420	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4898523e-05
2,930	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.8415815e-05
3,514	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.2429609e-05
3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.104636e-05
3,917	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9266831e-05
3,944	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	6.9105015e-05
4,976	Structural Trend Analysis for Online Social Networks	2011	VLDB	6.3313001e-05
4,979	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.3300966e-05
5,025	Finding Persistent Items in Data Streams	2017	VLDB	6.3093822e-05
5,652	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.0515502e-05
6,315	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.8161255e-05
6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7458578e-05
7,694	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.4764188e-05
7,697	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4754508e-05
7,965	Efficient Approximate Algorithms for Empirical Entropy and Mutual Information	2021	SIGMOD	5.4161136e-05
8,046	Authenticated Online Data Integration Services	2015	SIGMOD	5.4007578e-05
8,390	Thread Cooperation in Multicore Architectures for Frequency Counting over Multiple Data Streams	2009	VLDB	5.3412917e-05
8,415	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.3350162e-05
9,509	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.1707704e-05
11,304	Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing	2025	VLDB	4.9793485e-05
11,342	DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees	2025	VLDB	4.9793485e-05
12,005	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.9793485e-05
12,298	Runtime Optimization of Join Location in Parallel Data Management Systems	2017	VLDB	4.9793485e-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
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995
2,750	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0573403e-05
2,875	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.9193665e-05
3,038	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.7270848e-05
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
3,927	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.9192361e-05
4,097	Fast Data Stream Algorithms using Associative Memories	2007	SIGMOD	6.8092798e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,025	Finding Persistent Items in Data Streams	2017	VLDB
2	2,875	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS
3	8,764	Stream Frequency over Interval Queries	2019	VLDB
4	14,308	Mining Frequent Itemsets with Bit Strings and Trie	2002	VLDB
5	9,390	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS
6	11,945	Frequent Elements with Witnesses in Data Streams	2021	PODS
7	6,252	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
8	12,467	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD
9	4,778	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB
10	124	Approximate Frequency Counts over Data Streams	2002	VLDB