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: 1678
Venue: PODS
Year: 2016
Pagerank: 5.8746921e-05
Overall Rank: 6,454 | 55.73%
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,669	Data Streams with Bounded Deletions	2018	PODS	6.1278944e-05
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
10,162	On Sketching Trimmed Statistics	2026	PODS	5.093636e-05
11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS	5.093636e-05
11,759	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	5.093636e-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
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
161	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00027981772
393	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001934104
462	Sampling Large Databases for Association Rules	1996	VLDB	0.00018065337
558	An Efficient Algorithm for Mining Association Rules in Large Databases	1995	VLDB	0.00016530269
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010240222
1,825	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.6726613e-05
3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.2428869e-05
4,354	Online Association Rule Mining	1999	SIGMOD	6.7479905e-05
5,996	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	6.0150613e-05
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05

Semantically Similar Papers

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