Analysis of Predictive Spatio-Temporal Queries

Jimeng Sun

Department of Computer Science, HKUST

Given a set of objects S, a spatio-temporal window query q retrieves the objects of S that will intersect the window during the (future) interval qT. A nearest neighbor query q retrieves the objects of S closest to q during qT. Given a threshold d, a spatio-temporal join retrieves the pairs of objects from two datasets that will come within distance d from each other during qT. In this paper we present probabilistic cost models that estimate the selectivity of spatio-temporal window queries and joins, and the expected distance of the nearest neighbor(s). The models capture any query/object mobility combination (dynamic queries, dynamic objects or both) and any type of data (points and rectangles) in arbitrary dimensionality. In addition, we develop specialized spatio-temporal histograms, which perform clustering based on both location and velocity information, and can be incrementally maintained. Extensive performance evaluation verifies the accuracy of the cost models and the effectiveness of the histogram techniques.