An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

Summary: Optimal l1-heavy-hitters algorithm for insertion streams: returns all items with f_i≥φm, rejects those ≤(φ−ε)m, gives |f̂_i−f_i|≤εm, uses O(ε^{-1}log(1/φ)+φ^{-1}log n+log log m) bits and O(1) updates. Matches a proved space lower bound; also yields max-frequency estimation and comparison-based variants for rank-aggregation/voting. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h45a3eeaee3ccc2c2
Venue: PODS
Year: 2016
Pagerank: 5.7458578e-05
Overall Rank: 6,570 | 55.83%
DOI: 10.1145/2902251.2902284

Incoming Non-self Citations Over Time

Authors

1. Arnab Bhattacharyya (Indian Institute of Science)
2. Palash Dey (Indian Institute of Science)
3. David P. Woodruff (IBM)

BibTeX Citation

@inproceedings{bhattacharyya_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902284},
        doi = {10.1145/2902251.2902284},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bhattacharyya, Arnab and Dey, Palash and Woodruff, David P.},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,778	Data Streams with Bounded Deletions	2018	PODS	5.9977531e-05
6,395	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7998727e-05
7,697	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4754508e-05
10,379	On Sketching Trimmed Statistics	2026	PODS	4.9793485e-05
11,945	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.9793485e-05
12,062	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
164	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027412227
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
473	Sampling Large Databases for Association Rules	1996	VLDB	0.00017673931
573	An Efficient Algorithm for Mining Association Rules in Large Databases	1995	VLDB	0.00016173338
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015906635
909	Finding Frequent Items in Data Streams	2008	VLDB	0.00013125647
1,636	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010016656
1,874	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.4579757e-05
3,708	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.0812099e-05
4,444	Online Association Rule Mining	1999	SIGMOD	6.5980526e-05
6,121	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.8800995e-05
6,395	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7998727e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,381	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS
2	11,471	Streaming Algorithms with Few State Changes	2024	PODS
3	11,538	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
4	3,917	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
5	3,708	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS
6	6,395	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS
7	5,778	Data Streams with Bounded Deletions	2018	PODS
8	11,945	Frequent Elements with Witnesses in Data Streams	2021	PODS
9	9,719	Finding Heavy-Hitters with Optimal State Changes	2026	PODS
10	1,636	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS