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,716 | Weighted Reservoir Sampling from Distributed Streams | 2019 | PODS | 5.9692227e-05 |
| 6,603 | Continuous Matrix Approximation on Distributed Data | 2014 | VLDB | 4.9923197e-05 |
| 6,717 | Continuous Distributed Counting for Non-monotonic Streams | 2012 | PODS | 4.9459755e-05 |
| 7,452 | Distributed Online Tracking | 2015 | SIGMOD | 4.7218383e-05 |
| 11,436 | Model Counting meets F0 Estimation | 2021 | PODS | 4.1905499e-05 |
| 11,831 | Variability in Data Streams | 2016 | PODS | 4.1905499e-05 |
| 11,861 | Scalable Approximate Query Tracking over Highly Distributed Data Streams | 2016 | SIGMOD | 4.1905499e-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.00044753012 |
| 168 | Approximate Frequency Counts over Data Streams | 2002 | VLDB | 0.0003915627 |
| 398 | Mergeable Summaries | 2012 | PODS | 0.00024383201 |
| 743 | Distributed Top-K Monitoring | 2003 | SIGMOD | 0.00017318557 |
| 831 | Finding Frequent Items in Data Streams | 2008 | VLDB | 0.00016094846 |
| 1,642 | Communication-Efficient Distributed Monitoring of Thresholded Counts | 2006 | SIGMOD | 0.00011037826 |
| 2,934 | Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles | 2005 | SIGMOD | 7.8628636e-05 |
| 4,246 | Optimal Tracking of Distributed Heavy Hitters and Quantiles | 2009 | PODS | 6.318484e-05 |
| 6,474 | Sampling Based Algorithms for Quantile Computation in Sensor Networks | 2011 | SIGMOD | 5.0422176e-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.7351747e-05 |
| 1,642 | Communication-Efficient Distributed Monitoring of Thresholded Counts | 2006 | SIGMOD | 0.00011037826 |
| 743 | Distributed Top-K Monitoring | 2003 | SIGMOD | 0.00017318557 |
| 6,603 | Continuous Matrix Approximation on Distributed Data | 2014 | VLDB | 4.9923197e-05 |
| 4,969 | Relative Error Streaming Quantiles | 2021 | PODS | 5.790405e-05 |
| 11,831 | Variability in Data Streams | 2016 | PODS | 4.1905499e-05 |
| 9,280 | Ranking Distributed Probabilistic Data | 2009 | SIGMOD | 4.3604461e-05 |
| 7,452 | Distributed Online Tracking | 2015 | SIGMOD | 4.7218383e-05 |
| 4,246 | Optimal Tracking of Distributed Heavy Hitters and Quantiles | 2009 | PODS | 6.318484e-05 |
| 6,717 | Continuous Distributed Counting for Non-monotonic Streams | 2012 | PODS | 4.9459755e-05 |