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

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.