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)
Incoming Non-self Citations Over Time
Authors
- 1. Zengfeng Huang
- 2. Ke Yi
- 3. Qin Zhang
Incoming Citations (Sorted by Pagerank)
Showing 7 of 7 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,718 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 5.9749691e-05 |
| 6,602 | Continuous Matrix Approximation on Distributed Data | 2014 | VLDB | 4.9971153e-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 |
| 11,433 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1945683e-05 |
| 11,823 | Variability in Data Streams | 2016 | PODS | 4.1945683e-05 |
| 11,853 | Scalable Approximate Query Tracking over Highly Distributed Data Streams | 2016 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 126 | Space-Efficient Online Computation of Quantile Summaries | 2001 | SIGMOD | 0.00044744986 |
| 166 | Approximate Frequency Counts over Data Streams | 2002 | VLDB | 0.00039361552 |
| 402 | Mergeable Summaries | 2012 | PODS | 0.00024196343 |
| 745 | Distributed Top-K Monitoring | 2003 | SIGMOD | 0.00017330487 |
| 835 | Finding Frequent Items in Data Streams | 2008 | VLDB | 0.00016109621 |
| 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 |
| 4,249 | Optimal Tracking of Distributed Heavy Hitters and Quantiles | 2009 | PODS | 6.3245666e-05 |
| 6,495 | Sampling Based Algorithms for Quantile Computation in Sensor Networks | 2011 | SIGMOD | 5.0413486e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,401 | Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming | 2022 | VLDB | 4.7397228e-05 |
| 1,640 | Communication-Efficient Distributed Monitoring of Thresholded Counts | 2006 | SIGMOD | 0.0001104808 |
| 745 | Distributed Top-K Monitoring | 2003 | SIGMOD | 0.00017330487 |
| 6,602 | Continuous Matrix Approximation on Distributed Data | 2014 | VLDB | 4.9971153e-05 |
| 4,966 | Relative Error Streaming Quantiles | 2021 | PODS | 5.7959749e-05 |
| 11,823 | Variability in Data Streams | 2016 | PODS | 4.1945683e-05 |
| 9,274 | Ranking Distributed Probabilistic Data | 2009 | SIGMOD | 4.3646295e-05 |
| 7,453 | Distributed Online Tracking | 2015 | SIGMOD | 4.7263711e-05 |
| 4,249 | Optimal Tracking of Distributed Heavy Hitters and Quantiles | 2009 | PODS | 6.3245666e-05 |
| 6,716 | Continuous Distributed Counting for Non-monotonic Streams | 2012 | PODS | 4.9507254e-05 |