Randomized algorithms for tracking distributed count, frequencies, and ranks

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

  • Huang Zengfeng, Hong Kong University of Science and Technology, Hong Kong
  • Yi Ke, Hong Kong University of Science and Technology, Hong Kong
  • Qin Zhang
We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is the count-tracking problem, where there are k players, each holding a counter ni that gets incremented over time, and the goal is to track an ∑-approximation of their sum n=∑ini continuously at all times, using minimum communication. While the deterministic communication complexity of the problem is θ(k/ε • log N), where N is the final value of n when the tracking finishes, we show that with randomization, the communication cost can be reduced to θ(√k/ε • log N). Our algorithm is simple and uses only O(1) space at each player, while the lower bound holds even assuming each player has infinite computing power. Then, we extend our techniques to two related distributed tracking problems: frequency-tracking and rank-tracking, and obtain similar improvements over previous deterministic algorithms. Both problems are of central importance in large data monitoring and analysis, and have been extensively studied in the literature.
OriginalsprogEngelsk
TitelPODS '12 Proceedings of the 31st symposium on Principles of Database Systems
RedaktørerKrötzsch Markus , Benedikt Michael, Lenzerini Maurizio
Antal sider12
ForlagAssociation for Computing Machinery
Udgivelsesår2012
Sider295-306
ISBN (trykt)978-1-4503-1248-6
DOI
StatusUdgivet - 2012
Begivenhedsymposium on Principles of Database Systems - Scottsdale, Arizona, USA
Varighed: 21 maj 201223 maj 2012
Konferencens nummer: 31

Konference

Konferencesymposium on Principles of Database Systems
Nummer31
LandUSA
ByScottsdale, Arizona
Periode21/05/201223/05/2012

Se relationer på Aarhus Universitet Citationsformater

ID: 45941152