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.9105015e-05
Overall Rank: 3,944 | 73.49%
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,196	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.2346177e-05
6,833	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.6684547e-05
7,016	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS	5.6206282e-05
7,622	Distributed Online Tracking	2015	SIGMOD	5.4823129e-05
11,938	Model Counting meets F0 Estimation	2021	PODS	4.9793485e-05
12,321	Variability in Data Streams	2016	PODS	4.9793485e-05
12,349	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	4.9793485e-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
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
456	Mergeable Summaries	2012	PODS	0.0001791284
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016296423
909	Finding Frequent Items in Data Streams	2008	VLDB	0.00013125647
1,470	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD	0.00010560701
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4253671e-05
3,917	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9266831e-05
6,315	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.8161255e-05

Semantically Similar Papers

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