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: 1488
Venue: PODS
Year: 2009
Pagerank: 6.318484e-05
Overall Rank: 4,246 | 70.50%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Ke Yi
2. Qin Zhang

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,068	Optimal Sampling From Distributed Streams	2010	PODS	9.638573e-05
4,080	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4619407e-05
4,190	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	6.3677694e-05
5,910	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	5.2718714e-05
6,474	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0422176e-05
6,600	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9925547e-05
6,717	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	4.9459755e-05
7,452	Distributed Online Tracking	2015	SIGMOD	4.7218383e-05
8,493	Prediction-Based Geometric Monitoring Over Distributed Data Streams	2012	SIGMOD	4.494116e-05
11,831	Variability in Data Streams	2016	PODS	4.1905499e-05
11,965	Monitoring Distributed Streams using Convex Decompositions	2015	VLDB	4.1905499e-05

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
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072660894
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044753012
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022205608
743	Distributed Top-K Monitoring	2003	SIGMOD	0.00017318557
831	Finding Frequent Items in Data Streams	2008	VLDB	0.00016094846
874	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001568356
955	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015069776
1,006	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014684829
1,394	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012218557
1,642	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.00011037826
2,934	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8628636e-05
2,952	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8230109e-05
5,045	Shape Sensitive Geometric Monitoring	2008	PODS	5.7332856e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,068	Optimal Sampling From Distributed Streams	2010	PODS	9.638573e-05
6,717	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	4.9459755e-05
7,452	Distributed Online Tracking	2015	SIGMOD	4.7218383e-05
8,066	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	4.5899218e-05
6,415	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.064828e-05
11,831	Variability in Data Streams	2016	PODS	4.1905499e-05
4,190	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	6.3677694e-05
4,969	Relative Error Streaming Quantiles	2021	PODS	5.790405e-05
5,954	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2542261e-05
2,934	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8628636e-05