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: hde5bc0035c9758d8
Venue: PODS
Year: 2009
Pagerank: 0.00010016656
Overall Rank: 1,636 | 89.01%
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
456	Mergeable Summaries	2012	PODS	0.0001791284
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013794691
1,319	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011045888
2,282	A Platform for Scalable One-Pass Analytics using MapReduce	2011	SIGMOD	8.6964781e-05
4,446	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5969248e-05
5,196	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.2346177e-05
6,395	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	5.7998727e-05
6,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7458578e-05
6,833	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.6684547e-05
7,697	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4754508e-05
8,553	Sampling Big Ideas in Query Optimization	2023	PODS	5.3158971e-05
8,764	Stream Frequency over Interval Queries	2019	VLDB	5.2828968e-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 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
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015906635
909	Finding Frequent Items in Data Streams	2008	VLDB	0.00013125647
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
5,157	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.2494766e-05

Semantically Similar Papers

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