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.00013093314
Overall Rank: 911 | 93.90%
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
452	Mergeable Summaries	2012	PODS	0.00018032092
1,329	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011013041
1,639	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	9.9845484e-05
1,681	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.8821344e-05
1,903	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.383454e-05
2,430	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.4651179e-05
2,938	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.8224388e-05
3,525	Sketching Linear Classifiers over Data Streams	2018	SIGMOD	7.2156031e-05
3,667	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	7.0967962e-05
3,932	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.900511e-05
3,955	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	6.8843906e-05
5,002	Structural Trend Analysis for Online Social Networks	2011	VLDB	6.3073797e-05
5,005	Pyramid Sketch: a Sketch Framework for Frequency Estimation of Data Streams	2017	VLDB	6.3061786e-05
5,040	Finding Persistent Items in Data Streams	2017	VLDB	6.2901248e-05
5,664	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	6.0293278e-05
6,310	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.7992155e-05
6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7279868e-05
7,030	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.6006602e-05
7,714	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.4557265e-05
7,970	Efficient Approximate Algorithms for Empirical Entropy and Mutual Information	2021	SIGMOD	5.3997018e-05
8,058	Authenticated Online Data Integration Services	2015	SIGMOD	5.3824183e-05
8,411	Thread Cooperation in Multicore Architectures for Frequency Counting over Multiple Data Streams	2009	VLDB	5.3213581e-05
8,440	Optimal Approximate Matrix Multiplication over Sliding Windows	2026	VLDB	5.3148581e-05
8,574	Panakos: Chasing the Tails for Multidimensional Data Streams	2023	VLDB	5.297131e-05
10,335	DobLIX: A Dual-Objective Learned Index for Log-Structured Merge Trees	2025	VLDB	5.0225409e-05
11,366	Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing	2025	VLDB	4.9605343e-05
12,055	In the Land of Data Streams where Synopses are Missing, One Framework to Bring Them All	2021	VLDB	4.9605343e-05
12,347	Runtime Optimization of Join Location in Parallel Data Management Systems	2017	VLDB	4.9605343e-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.00036097627
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
861	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013374869
2,738	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0599809e-05
2,887	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.8903242e-05
3,049	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.6987705e-05
3,091	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6394636e-05
3,931	Statistical Analysis of Sketch Estimators	2007	SIGMOD	6.900756e-05
4,115	Fast Data Stream Algorithms using Associative Memories	2007	SIGMOD	6.785832e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,040	Finding Persistent Items in Data Streams	2017	VLDB
2	2,887	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS
3	8,792	Stream Frequency over Interval Queries	2019	VLDB
4	14,353	Mining Frequent Itemsets with Bit Strings and Trie	2002	VLDB
5	9,425	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS
6	11,995	Frequent Elements with Witnesses in Data Streams	2021	PODS
7	6,267	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
8	12,516	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD
9	4,799	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