Multi-dimensional online tracking

摘要

We propose and study a new class of online problems, which we call online tracking. Suppose an observer, say Alice, observes a multi-valued function f: Z+ → Zd overtime in an online fashion, i.e., she only sees f(t) for t ≤ tnow where tnow is the current time. She would like to keep a tracker, say Bob, informed of the current value of f at all times. Under this setting, Alice could send new values of f to Bob from time to time, so that the current value of f is always within a distance of Δ to the last value received by Bob. We give competitive online algorithms whose communication costs are compared with the optimal offline algorithm that knows the entire f in advance. We also consider variations of the problem where Alice is allowed to send 'predictions' to Bob, to further reduce communication for well-behaved functions. These online trackingproblems have a variety of application ranging from sensor monitoring, location-based services, to publish/subscribe systems.