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: 1679
Venue: PODS
Year: 2016
Pagerank: 5.0696932e-05
Overall Rank: 6,418 | 55.36%
DOI: 10.1145/2902251.2902284

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,884	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	7.9620506e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
11,562	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.1945683e-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
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
181	Mining Frequent Patterns without Candidate Generation	2000	SIGMOD	0.00036992674
472	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.00022346384
473	Sampling Large Databases for Association Rules	1996	VLDB	0.0002233798
547	An Efficient Algorithm for Mining Association Rules in Large Databases	1995	VLDB	0.00020420717
597	Computing Iceberg Queries Efficiently	1998	VLDB	0.00019475592
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
1,955	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD	9.9629452e-05
2,884	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	7.9620506e-05
3,660	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	6.8691367e-05
4,258	Online Association Rule Mining	1999	SIGMOD	6.3148619e-05
5,902	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.2796864e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
4,403	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2194225e-05
10,901	Streaming Algorithms with Few State Changes	2024	PODS	4.1945683e-05
10,983	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1945683e-05
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
3,660	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	6.8691367e-05
2,884	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	7.9620506e-05
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
10,005	Finding Heavy-Hitters with Optimal State Changes	2026	PODS	4.1945683e-05
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267