Space-optimal Heavy Hitters with Strong Error Bounds

Summary: Shows FREQUENT/SpaceSaving get a tail guarantee: per-item error depends only on the L1 mass of the tail, not on top frequencies, making them space-optimal under this stronger bound. Implies O(k) space sparse recovery with near-optimal L1 error (improving O(k log n)) and gives guarantees for Zipfian data and mergeable summaries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1486
Venue: PODS
Year: 2009
Pagerank: 0.00010240222
Overall Rank: 1,600 | 89.03%
DOI: 10.1145/1559795.1559819

Incoming Non-self Citations Over Time

Authors

1. Radu Berinde (Massachusetts Institute of Technology)
2. Graham Cormode (AT&T)
3. Piotr Indyk (Massachusetts Institute of Technology)
4. Martin J. Strauss (University of Michigan)

BibTeX Citation

@inproceedings{berinde_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Space-optimal Heavy Hitters with Strong Error Bounds}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559819},
        doi = {10.1145/1559795.1559819},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Berinde, Radu and Cormode, Graham and Indyk, Piotr and Strauss, Martin J.},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
451	Mergeable Summaries	2012	PODS	0.00018151445
777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001410593
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
2,265	A Platform for Scalable One-Pass Analytics using MapReduce	2011	SIGMOD	8.8398946e-05
4,370	Fast Manhattan Sketches in Data Streams	2010	PODS	6.7387541e-05
5,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
6,275	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.9299343e-05
6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.8746921e-05
6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.7985588e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
8,379	Sampling Big Ideas in Query Optimization	2023	PODS	5.4378437e-05
8,603	Stream Frequency over Interval Queries	2019	VLDB	5.4041343e-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 7 of 7 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
393	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001934104
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
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
5,036	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.3915389e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
2	4,472	Relative Error Streaming Quantiles	2021	PODS
3	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
4	122	Approximate Frequency Counts over Data Streams	2002	VLDB
5	5,669	Data Streams with Bounded Deletions	2018	PODS
6	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
7	12,176	Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams	2014	SIGMOD
8	8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB
9	3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS
10	6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS