DIMACS TR: 2003-11

Radial Histograms for Spatial Streams

Authors: Graham Cormode and S. Muthukrishnan


Many data streams relate to geographic or spatial information such as the tracking of moving objects, or location-specific measurements and queries. While several techniques have been developed recently for processing numerical, text or XML streams, new techniques are needed to process spatial queries on streaming geometric data.

We propose a novel data structure, the Radial Histogram, to process streams including spatial data points. It allows a number of geometric aggregates involving the spread and extent of the points in the data streams---diameter, furthest neighbors, convex hulls---to be accurately estimated to arbitrary precision. By using multiple Radial Histograms for a set of given facilities, we can process data streams consisting of massive numbers of client points. We can then accurately estimate number of spatial aggregates involving relative placement of clients with respect to the facilities, including reverse nearest neighbors, spatial joins and more.

Radial histograms use very small space and are exceedingly simple to implement. Nevertheless, we prove that they guarantee accurate estimation for spatial aggregate queries mentioned above. An experimental evaluation shows them to perform very well in practice.

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

DIMACS Home Page