Database Paper Browser

Back to papers

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
1487
Venue
PODS
Year
2009
Pagerank
0.00011085267
Overall Rank
1,629 | 88.67%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank Citing Paper Year Venue Pagerank
402 Mergeable Summaries 2012 PODS 0.00024196343
1,094 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.00014129658
1,584 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011255801
2,476 A Platform for Scalable One-Pass Analytics using MapReduce 2011 SIGMOD 8.6960139e-05
2,884 BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory 2017 PODS 7.9620506e-05
3,566 Fast Manhattan Sketches in Data Streams 2010 PODS 6.9629443e-05
4,718 Weighted Reservoir Sampling from Distributed Streams 2019 PODS 5.9749691e-05
6,418 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS 5.0696932e-05
6,602 Continuous Matrix Approximation on Distributed Data 2014 VLDB 4.9971153e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5596344e-05
8,470 Sampling Big Ideas in Query Optimization 2023 PODS 4.5038423e-05
8,594 Stream Frequency over Interval Queries 2019 VLDB 4.4891331e-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
Previous Page 1 / 1 Next

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
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
472 Bottom-Up Computation of Sparse and Iceberg CUBEs 1999 SIGMOD 0.00022346384
597 Computing Iceberg Queries Efficiently 1998 VLDB 0.00019475592
835 Finding Frequent Items in Data Streams 2008 VLDB 0.00016109621
1,955 Efficient Computation of Iceberg Cubes with Complex Measures 2001 SIGMOD 9.9629452e-05
3,660 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS 6.8691367e-05
5,016 Finding Hierarchical Heavy Hitters in Data Streams 2003 VLDB 5.7580375e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
848 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.0001597308
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,966 Relative Error Streaming Quantiles 2021 PODS 5.7959749e-05
12,108 Space-Efficient Estimation of Statistics over Sub-Sampled Streams 2012 PODS 4.1945683e-05
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
11,440 Frequent Elements with Witnesses in Data Streams 2021 PODS 4.1945683e-05
11,978 Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams 2014 SIGMOD 4.1945683e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5596344e-05
3,660 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS 6.8691367e-05
6,418 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS 5.0696932e-05