Analysis of predictive spatio-temporal queries

Yufei Tao, Jimeng Sun, Dimitris Papadias

Research output: Contribution to journalArticlepeer-review


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 article, we present probabilistic cost models that estimate the selectivity of spatio-temporal window queries and joins, and the expected distance between a query and its nearest neighbor(s). Our models capture any query/object mobility combination (moving queries, moving objects or both) and any data type (points and rectangles) in arbitrary dimensionality. In addition, we develop specialized spatio-temporal histograms, which take into account both location and velocity information, and can be incrementally maintained. Extensive performance evaluation verifies that the proposed techniques produce highly accurate estimation on both uniform and non-uniform data.

Original languageEnglish (US)
Pages (from-to)295-336
Number of pages42
JournalACM Transactions on Database Systems
Issue number4
StatePublished - Dec 2003
Externally publishedYes


  • Database
  • Histogram
  • Nearest distance
  • Selectivity
  • Spatio-temporal

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Analysis of predictive spatio-temporal queries'. Together they form a unique fingerprint.

Cite this