Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks

作     者：Huang, Zengfeng Yi, Ke Zhang, Qin 

作者机构：Fudan Univ Sch Data Sci Shanghai Peoples R China Hong Kong Univ Sci & Technol Clear Water Bay Hong Kong Peoples R China Indiana Univ Bloomington IN USA 

出 版 物：《ALGORITHMICA》 (算法)

年 卷 期：2019年第81卷第6期

页      面：2222-2243页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation, NSF, (1844234) Shanghai Science and Technology Development Foundation, (18YF1401200) National Natural Science Foundation of China, (61802069) Research Grants Council, University Grants Committee, RGC, UGC, (GRF-16200415, GRF-16211614, GRF-621413) 

主　　题：Continuous distributed tracking Randomized algorithms Distributed streaming 

摘      要：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 epsilon-approximation of their sum n=Sigma ini continuously at all times, using minimum communication. While the deterministic communication complexity of the problem is (k/epsilonlogN), where N is the final value of n when the tracking finishes, we show that with randomization, the communication cost can be reduced to epsilonlogN). 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.