Multi-dimensional online tracking
Ke Yi, Qin Zhang · 2009
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 + → Z d over time 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 tracking problems have a variety of application ranging from sensor monitoring, location-based services, to publish/subscribe systems. 1