Title: Multi-Dimensional Online Tracking

Speaker:  Qin Zhang
HKUST

Date: Friday, October 3, 2008
Time 11:00-11:50
Venue: Room 3464, HKUST

Abstract: We propose and study a new class of online problems, 
which we call {\em online tracking}.  Suppose an {\em observer}, 
say Alice, observes a multi-valued function 
$f : \mathbb{Z}^+ \rightarrow \mathbb{Z}^d$ 
over time in an online fashion, i.e., she only sees 
$f(t)$ for $t\le\tnow$ where $\tnow$ is the current time.  
She would like to keep a {\em 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 $\Delta$ 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.

This is joint work with Ke Yi.