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: 1585
Venue: PODS
Year: 2012
Pagerank: 7.0690791e-05
Overall Rank: 3,856 | 73.55%
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,068	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.3770298e-05
6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB	5.7985588e-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
11,631	Model Counting meets F0 Estimation	2021	PODS	5.093636e-05
12,026	Variability in Data Streams	2016	PODS	5.093636e-05
12,054	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	5.093636e-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.00036378991
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
451	Mergeable Summaries	2012	PODS	0.00018151445
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
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
3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	7.0856664e-05
6,178	Sampling Based Algorithms for Quantile Computation in Sensor Networks	2011	SIGMOD	5.949619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,488	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB
2	1,433	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD
3	550	Distributed Top-K Monitoring	2003	SIGMOD
4	6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB
5	4,472	Relative Error Streaming Quantiles	2021	PODS
6	12,026	Variability in Data Streams	2016	PODS
7	9,425	Ranking Distributed Probabilistic Data	2009	SIGMOD
8	7,479	Distributed Online Tracking	2015	SIGMOD
9	3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
10	6,871	Continuous Distributed Counting for Non-monotonic Streams	2012	PODS