Distributed Online Tracking

In online tracking, an observer S receives a sequence of values, one per time instance, from a data source that is de-scribed by a function f. A tracker T wants to continuously maintain an approximation that is within an error threshold of the value f(t) at any time instance t, with small commu-nication overhead. This problem was recently formalized and studied in [32, 34], and a principled approach with op-timal competitive ratio was proposed. This work extends the study of online tracking to a distributed setting, where a tracker T wants to track a function f that is computed from a set of functions {f1,..., fm} from m distributed ob-servers and respective data sources. This formulation finds numerous important and natural applications, e.g., sensor networks, distributed systems, measurement networks, and pub-sub systems. We formalize this problem and present effective online algorithms for various topologies of a dis-tributed system/network for different aggregate functions. Experiments on large real data sets demonstrate the excel-lent performance of our methods in practice