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.3245666e-05
Overall Rank: 4,249 | 70.45%
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,080	Optimal Sampling From Distributed Streams	2010	PODS	9.5899129e-05
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
4,190	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	6.3739017e-05
5,909	At-the-time and Back-in-time Persistent Sketches	2021	SIGMOD	5.2769377e-05
6,495	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.0413486e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
6,716	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	4.9507254e-05
7,453	Distributed Online Tracking	2015	SIGMOD	4.7263711e-05
8,495	Prediction-Based Geometric Monitoring Over Distributed Data Streams	2012	SIGMOD	4.4984289e-05
11,823	Variability in Data Streams	2016	PODS	4.1945683e-05
11,957	Monitoring Distributed Streams using Convex Decompositions	2015	VLDB	4.1945683e-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.00072723062
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
477	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00022221803
745	Distributed Top-K Monitoring	2003	SIGMOD	0.00017330487
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
865	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00015808172
956	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00015066967
1,003	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014698435
1,392	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012229045
1,640	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.0001104808
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
5,051	Shape Sensitive Geometric Monitoring	2008	PODS	5.7340225e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,080	Optimal Sampling From Distributed Streams	2010	PODS	9.5899129e-05
6,716	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	4.9507254e-05
7,453	Distributed Online Tracking	2015	SIGMOD	4.7263711e-05
8,062	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	4.5943269e-05
6,418	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.0696932e-05
11,823	Variability in Data Streams	2016	PODS	4.1945683e-05
4,190	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	6.3739017e-05
4,966	Relative Error Streaming Quantiles	2021	PODS	5.7959749e-05
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
2,931	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	7.8697258e-05