Distributed Online Tracking


In online tracking, an observer <i>S</i> receives a sequence of values, one per time instance, from a data source that is described by a function <i>f</i>. A tracker <i>T</i> wants to continuously maintain an approximation that is within an error threshold of the value <i>f</i>(<i>t</i>) at any time instance <i>t</i>, with small communication overhead. This problem was recently formalized and studied, and a principled approach with optimal 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 <i>f</i>1 , . . . , <i>f<sub>m</sub></i> from <i>m</i> distributed observers 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 distributed system/network for different aggregate functions. Experiments on large real data sets demonstrate the excellent performance of our methods in practice.


    13 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)