2004-28: Location Streams: Models and Algorithms

DIMACS TR: 2004-28

Location Streams: Models and Algorithms

Authors: M. Hoffman, S. Muthukrishnan and Rajeev Raman

ABSTRACT 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 objects. 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 general by initating the study of new models and algoritms for spatial data such as location streams.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-28.ps.gz

DIMACS Home Page