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.00010694459
Overall Rank
1,744 | 87.89%
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
398 Mergeable Summaries 2012 PODS 0.00024383201
1,117 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.0001386123
1,586 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD 0.00011245213
2,476 A Platform for Scalable One-Pass Analytics using MapReduce 2011 SIGMOD 8.6907971e-05
3,557 Fast Manhattan Sketches in Data Streams 2010 PODS 6.9711051e-05
4,716 Weighted Reservoir Sampling from Distributed Streams 2019 PODS 5.9692227e-05
6,347 BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory 2017 PODS 5.0969206e-05
6,415 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS 5.064828e-05
6,603 Continuous Matrix Approximation on Distributed Data 2014 VLDB 4.9923197e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5552628e-05
8,467 Sampling Big Ideas in Query Optimization 2023 PODS 4.4995247e-05
8,592 Stream Frequency over Interval Queries 2019 VLDB 4.4848323e-05
11,443 Frequent Elements with Witnesses in Data Streams 2021 PODS 4.1905499e-05
11,566 Timely Reporting of Heavy Hitters using External Memory 2020 SIGMOD 4.1905499e-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
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
475 Bottom-Up Computation of Sparse and Iceberg CUBEs 1999 SIGMOD 0.00022238407
598 Computing Iceberg Queries Efficiently 1998 VLDB 0.00019431661
831 Finding Frequent Items in Data Streams 2008 VLDB 0.00016094846
1,967 Efficient Computation of Iceberg Cubes with Complex Measures 2001 SIGMOD 9.9108189e-05
3,701 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS 6.825442e-05
5,188 Finding Hierarchical Heavy Hitters in Data Streams 2003 VLDB 5.635103e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
846 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00015949293
10,986 A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024 SIGMOD 4.1905499e-05
4,969 Relative Error Streaming Quantiles 2021 PODS 5.790405e-05
12,116 Space-Efficient Estimation of Statistics over Sub-Sampled Streams 2012 PODS 4.1905499e-05
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
11,443 Frequent Elements with Witnesses in Data Streams 2021 PODS 4.1905499e-05
11,986 Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams 2014 SIGMOD 4.1905499e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5552628e-05
3,701 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS 6.825442e-05
6,415 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS 5.064828e-05