DBScholar

Back to papers

Optimal Tracking of Distributed Heavy Hitters and Quantiles

Summary: Algorithms for tracking φ-heavy hitters and φ-quantiles in the k-site coordinator distributed streaming model with worst-case communication O((k/ε) log n), substantially improving prior bounds. Matching lower bounds prove optimality; also handles all φ-quantiles simultaneously. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1487
Venue
PODS
Year
2009
Pagerank
7.0856664e-05
Overall Rank
3,832 | 73.72%
DOI
10.1145/1559795.1559820

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{yi_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Optimal Tracking of Distributed Heavy Hitters and Quantiles}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559820},
        doi = {10.1145/1559795.1559820},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Yi, Ke and Zhang, Qin},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
2,178 Optimal Sampling From Distributed Streams 2010 PODS 9.0159538e-05
3,765 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 7.1442477e-05
3,856 Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks 2012 PODS 7.0690791e-05
5,255 At-the-time and Back-in-time Persistent Sketches 2021 SIGMOD 6.2982495e-05
6,178 Sampling Based Algorithms for Quantile Computation in Sensor Networks 2011 SIGMOD 5.949619e-05
6,871 Continuous Distributed Counting for Non-monotonic Streams 2012 PODS 5.7496345e-05
7,479 Distributed Online Tracking 2015 SIGMOD 5.6081446e-05
7,548 Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory 2024 SIGMOD 5.6021153e-05
8,501 Prediction-Based Geometric Monitoring Over Distributed Data Streams 2012 SIGMOD 5.4132745e-05
10,186 Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees 2026 SIGMOD 5.093636e-05
12,026 Variability in Data Streams 2016 PODS 5.093636e-05
12,155 Monitoring Distributed Streams using Convex Decompositions 2015 VLDB 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
26 Models and Issues in Data Stream Systems 2002 PODS 0.00052982574
82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00036378991
122 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00031260115
337 Model-Driven Data Acquisition in Sensor Networks 2004 VLDB 0.00020783399
550 Distributed Top-K Monitoring 2003 SIGMOD 0.0001663758
722 Adaptive Filters for Continuous Queries over Distributed Data Streams 2003 SIGMOD 0.00014627248
838 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.0001370404
842 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00013671191
885 Finding Frequent Items in Data Streams 2008 VLDB 0.00013419017
1,045 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.00012440928
1,433 Communication-Efficient Distributed Monitoring of Thresholded Counts 2006 SIGMOD 0.0001080304
2,406 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.6187297e-05
2,716 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 8.2108958e-05
4,989 Shape Sensitive Geometric Monitoring 2008 PODS 6.4106441e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,178 Optimal Sampling From Distributed Streams 2010 PODS
2 6,871 Continuous Distributed Counting for Non-monotonic Streams 2012 PODS
3 7,479 Distributed Online Tracking 2015 SIGMOD
4 8,005 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD
5 6,454 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS
6 12,026 Variability in Data Streams 2016 PODS
7 3,856 Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks 2012 PODS
8 4,472 Relative Error Streaming Quantiles 2021 PODS
9 5,599 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS
10 2,406 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD