HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/172
Title: The TPR*-tree : an optimized spatio-temporal access method for predictive queries
Authors: Tao, Yufei
Papadias, Dimitris
Sun, Jimeng
Keywords: Spatio-temporal
TPR-tree
Predictive
Queries
Algorithms
Issue Date: 2003
Citation: To be published in Very large data bases : Proceedings, Berlin, Germany, 9-12 Sep. 2003
Abstract: 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.
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
URI: http://hdl.handle.net/1783.1/172
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
VLDB03TPR.pdf187KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.