DBScholar

Back to papers

Timely Reporting of Heavy Hitters using External Memory

Summary: External-memory TED: real-time reporting of phi-heavy hitters with zero false negatives at their T-th occurrence. External-memory structures provide accuracy, sensitivity, and timeliness with tunable delay; logarithmic I/O under bounded delay; scales to 11M obs/sec. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5873
Venue
SIGMOD
Year
2020
Pagerank
5.093636e-05
Overall Rank
11,759 | 19.33%
DOI
10.1145/3318464.3380598

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

BibTeX Citation

@inproceedings{pandey_sigmod20,
        title = {{Timely Reporting of Heavy Hitters using External Memory}},
        author = {Pandey, Prashant and Singh, Shikha and Bender, Michael A. and Berry, Jonathan W. and Farach-Colton, Martín and Johnson, Rob and Kroeger, Thomas M. and Phillips, Cynthia A.},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380598},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380598},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank Citing Paper Year Venue Pagerank
3,798 Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design 2021 SIGMOD 7.1165678e-05
8,892 Adaptive Quotient Filters 2024 SIGMOD 5.3505412e-05
10,426 Aeris Filter: A Strongly and Monotonically Adaptive Range Filter 2026 SIGMOD 5.093636e-05
10,434 Breadcrumb Filters: Fast Fully Featured Filters 2026 SIGMOD 5.093636e-05
10,799 Zombie Hashing: Reanimating Tombstones in a Graveyard 2025 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
789 Don't Thrash: How to Cache Your Hash on Flash 2012 VLDB 0.0001401724
832 Streaming Queries over Streaming Data 2002 VLDB 0.00013736125
838 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.0001370404
1,112 Cache-Oblivious String B-trees 2006 PODS 0.00012125766
1,600 Space-optimal Heavy Hitters with Strong Error Bounds 2009 PODS 0.00010240222
1,825 Efficient Computation of Iceberg Cubes with Complex Measures 2001 SIGMOD 9.6726613e-05
2,043 A General-Purpose Counting Filter: Making Every Bit Count 2017 SIGMOD 9.2674387e-05
3,628 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS 7.2428869e-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
11,970 Write-Optimized Skip Lists 2017 PODS 5.093636e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,537 Finding Heavy-Hitters with Optimal State Changes 2026 PODS
2 12,056 Range Thresholding on Streams 2016 SIGMOD
3 6,204 Complete Event Trend Detection in High-Rate Event Streams 2017 SIGMOD
4 11,123 Streaming Algorithms with Few State Changes 2024 PODS
5 885 Finding Frequent Items in Data Streams 2008 VLDB
6 10,910 Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing 2025 VLDB
7 6,454 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS
8 11,638 Frequent Elements with Witnesses in Data Streams 2021 PODS
9 11,196 A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024 SIGMOD
10 3,628 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS