DIMACS TR: 2004-28
Location Streams: Models and Algorithms
Authors: M. Hoffman, S. Muthukrishnan and Rajeev Raman
We propose two new data stream models: the reset model and the delta model.
These are suitable for processing data streams comprising locations of moving
We present algorithms for tracking the ``extent'' of such points in both
these models that fits the stream constraint of polylogarithmic space and
time. Our work adds to the growing knowledge of data stream algorithms in
by initating the study of new models and algoritms for spatial data such
as location streams.
Paper Available at:
DIMACS Home Page