Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/172

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

Authors Tao, Tao
Papadias, Dimitris
Sun, Jimeng
Issue Date 2003
Source Proceedings of the Very Large Data Bases Conference (VLDB), Berlin, September 9-12, Morgan Kaufmann, pp. 790-801
Summary A predictive spatio-temporal query retrieves the set of moving objects that will intersect a query window during a future time interval. Currently, the only access method for processing such queries in practice is the TPR-tree. In this paper we first perform an analysis to determine the factors that affect the performance of predictive queries and show that several of these factors are not considered by the TPR-tree, which uses the insertion/deletion algorithms of the R*-tree designed for static data. Motivated by this, we propose 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. In addition, we provide cost models that determine the optimal performance achievable by any data-partition spatio-temporal access method. Using experimental comparison, we illustrate that the TPR*-tree is nearly-optimal and significantly outperforms the TPR-tree under all conditions.
Subjects
Rights This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder
Language English
Format Conference paper
Access
Files in this item:
File Description Size Format
VLDB03TPR.pdf 187.29 kB Adobe PDF