The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries

Yufei Tao, Dimitris Papadias, Jimeng Sun

Research output: Chapter in Book/Report/Conference proceedingChapter


This chapter performs an analysis to determine the factors that affect the performance of predictive queries and shows that several of these factors are not considered by the Time Parameterized R-tree (TPR-tree), which uses the insertion/deletion algorithms of the R-tree designed for static data. A predictive spatio-temporal query retrieves the set of moving objects that will intersect a query window during a future time interval. The chapter proposes a new index structure called the TPR*-tree, which takes into account the unique features of dynamic objects through a set of improved construction algorithms. The TPR*-tree improves the TPR-tree by employing a new set of insertion and deletion algorithms. In addition, it provides cost models that determine the optimal performance achievable by any data-partition spatio-temporal access method. Using experimental comparison, it illustrates that the TPR-tree is nearly-optimal and significantly outperforms the TPR*-tree under all conditions.

Original languageEnglish (US)
Title of host publicationProceedings 2003 VLDB Conference
Subtitle of host publication29th International Conference on Very Large Databases (VLDB)
Number of pages12
ISBN (Electronic)9780127224428
StatePublished - Jan 1 2003
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries'. Together they form a unique fingerprint.

Cite this