Learning Based Distributed Tracking
Aug 13, 20207 views
Inspired by the great success of machine learning in the past decade,,people have been thinking about the possibility of improving the,theoretical results by exploring data distribution. In this paper,,we revisit a fundamental problem called,Distributed Tracking,(DT),under an assumption that the data follows a certain (known or,unknown) distribution, and propose a number,data-dependent,algorithms with improved theoretical bounds. Informally, in the DT,problem, there is a coordinator and,k,players, where the coordinator,holds a threshold,N,and each player has a counter. At each time,stamp, at most one counter can be increased by one. The job of the,coordinator is to capture the exact moment when the sum of all,these,k,counters reaches,N,. The goal is to minimise the communication cost. While our first type of algorithms assume the concrete,data distribution is,known in advance,, our second type of algorithms can learn the distribution on the fly. Both of the algorithms,achieve a communication cost bounded by,O,(,k,log log,N,),with high,probability, improving the state-of-the-art,data-independent,bound,O,(,k,log,N,k,),. We further propose a number of implementation optimisation heuristics to improve both efficiency and robustness of,the algorithms. Finally, we conduct extensive experiments on three,real datasets and four synthetic datasets. The experimental results,show that the communication cost of our algorithms is as least as,20%,of that of the state-of-the-art algorithms.