Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks

Summary: Randomized protocols reduce communication for continuous distributed count-tracking from Θ(k/ε · log N) to Θ(√k/ε · log N) with O(1) space per player and a matching lower bound. Technique extends to frequency- and rank-tracking giving analogous √k improvements over deterministic algorithms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hdb1379b6b9256dad
Venue: PODS
Year: 2012
Pagerank: 6.8843906e-05
Overall Rank: 3,955 | 73.50%
DOI: 10.1145/2213556.2213596

Incoming Non-self Citations Over Time

Authors

1. Zengfeng Huang (Hong Kong University of Science and Technology)
2. Ke Yi (Hong Kong University of Science and Technology)
3. Qin Zhang (Aarhus University)

BibTeX Citation

@inproceedings{huang_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213596},
        doi = {10.1145/2213556.2213596},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Huang, Zengfeng and Yi, Ke and Zhang, Qin},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,222	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.2110605e-05
6,856	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.6470368e-05
7,037	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.5993909e-05
7,643	Distributed Online Tracking	2015	SIGMOD	5.4615983e-05
11,988	Model Counting meets F0 Estimation	2021	PODS	4.9605343e-05
12,370	Variability in Data Streams	2016	PODS	4.9605343e-05
12,398	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036097627
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
452	Mergeable Summaries	2012	PODS	0.00018032092
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016238411
911	Finding Frequent Items in Data Streams	2008	VLDB	0.00013093314
1,471	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.00010529345
2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.3988741e-05
3,932	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.900511e-05
6,310	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.7992155e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,648	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB
2	1,471	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD
3	565	Distributed Top-K Monitoring	2003	SIGMOD
4	6,856	Continuous Matrix Approximation on Distributed Data	2014	VLDB
5	4,279	Relative Error Streaming Quantiles	2021	PODS
6	12,370	Variability in Data Streams	2016	PODS
7	9,644	Ranking Distributed Probabilistic Data	2009	SIGMOD
8	7,643	Distributed Online Tracking	2015	SIGMOD
9	3,932	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
10	7,037	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS