Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
复制标题
DOI：
10.1007/s00453-018-00531-y
复制
发表时间：
2011-08
期刊：
影响因子：
1.1
通讯作者：
Zengfeng Huang;K. Yi;Qin Zhang
中科院分区：
文献类型：
--
作者：
Zengfeng Huang;K. Yi;Qin Zhang
我们表明，随机化可以导致显着改善分布式跟踪的一些基本问题。我们的基础是计数跟踪问题，这里有k个参与者，每个参与者都有一个计数器，随着时间的推移而递增，目标是在任何时候都连续跟踪他们的和的近似值，使用最少的通信。而确定性的通信复杂性的问题，其中N是最终值n时，跟踪完成，我们表明，与随机化，通信成本可以减少到。我们的算法是简单的，在每个参与人只使用O（1）空间，而下界保持即使假设每个参与人有无限的计算能力。然后，我们将我们的技术扩展到两个相关的分布式跟踪问题：频率跟踪和秩跟踪，并获得类似的改进，以前的确定性算法。这两个问题在大数据监测和分析中具有核心重要性，并且在文献中已被广泛研究。
We show that randomization can lead to significant improvements for a few fundamental problems in distributed tracking. Our basis is thecount-trackingproblem, where there arekplayers, each holding a counterthat gets incremented over time, and the goal is to track an-approximation of their sumcontinuously at all times, using minimum communication. While the deterministic communication complexity of the problem is, whereNis the final value ofnwhen the tracking finishes, we show that with randomization, the communication cost can be reduced to. Our algorithm is simple and uses onlyO(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-trackingandrank-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.