Abstract
We present a new technique called STAR-tree, based on R*-tree, for indexing a set of moving points so that various queries, including range queries, time-slice queries, and nearest-neighbor queries, can be answered efficiently. A novel feature of the index is that it is self-adjusting in the sense that it re-organizes itself locally whenever its query performance deteriorates. The index provides tradeoffs between storage and query performance and between time spent in updating the index and in answering queries. We present detailed performance studies and compare our methods with the existing ones under a varying type of data sets and queries. Our experiments show that the index proposed here performs considerably better than the previously known ones.
C.P. is supported by Army Research Office MURI grant DAAH04-96-1-0013 and an NSF grant CCR-9732787. P.A. is supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by NSF grants ITR-333-1050, EIA-9870724, EIA-997287, and CCR-9732787, and by a grant from the U.S.-Israeli Binational Science Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P. K. Agarwal, L. Arge, and J. Erickson, Indexing moving points, Proc. Annu. ACM Sympos. Principles Database Syst., 2000. 175–186.
P. K. Agarwal, J. Erickson, and L. J. Guibas, Kinetic BSPs for intersecting segments and disjoint triangles, Proc. 9th ACM-SIAM Sympos. Discrete Algorithms, 1998, pp. 107–116.
P. K. Agarwal and S. Har-Peled, Maintaining approximate extent measures of moving points, Proc. 12th ACM-SIAM Sympos. Discrete Algorithms, 2001.
L. Arge, R. Barve, D. Hutchinson, O. Procopiuc, L. Toma, D. E. Vengroff, and R. Wickeremesinghe, TPIE User Manual and Reference (edition 0.9.01b). Duke University, 1999. The manual and software distribution are available on the web at http://www.cs.duke.edu/TPIE/.
J. Basch, L. J. Guibas, and J. Hershberger, Data structures for mobile data, Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, 1997, pp. 747–756.
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, The R*-tree: An efficient and robust access method for points and rectangles, Proc. ACM SIGMOD Conf. on Management of Data, 1990, pp. 322–331.
D. H. Douglas and T. K. Peucker, Algorithms for the reduction of the number of points required to represent a digitized line or its caricature, Canadian Cartographer, 10 (1973), pp. 112–122.
R. H. Güting, M. H. Böhlen, M. Erwig, C. S. Jensen, N. A. Lorentzos, M. Schneider, and M. Vazirgiannis, A foundation for representing and querying moving objects, ACM Trans. Database Systems, 25 (2000), pp. 1–42.
M. I. Karavelas and L. J. Guibas, Static and kinetic geometric spanners with applications, Proc. 12th Annu. ACM-SIAM Sympos. Discrete Algorithms, 2001, pp. 168–176.
G. Kollios, D. Gunopulos, and V. J. Tsotras, On indexing mobile objects, Proc. Annu. ACM Sympos. Principles Database Syst., 1999, pp. 261–272.
S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez, Indexing the positions of continuously moving objects, Proc. ACM SIGMOD International Conference on Management of Data, 2000, pp. 331–342.
A. P. Sistla and O. Wolfson, Temporal conditions and integrity constraints in active database systems, Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, 1995, pp. 269–280.
A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao, Modeling and querying moving objects, Proc. Intl Conf. Data Engineering, 1997, pp. 422–432.
J. Tayeb, O. Ulusoy, and O. Wolfson, A quadtree-based dynamic attribute indexing method, The Computer Journal, (1998), 185–200.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Procopiuc, C.M., Agarwal, P.K., Har-Peled, S. (2002). STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects. In: Mount, D.M., Stein, C. (eds) Algorithm Engineering and Experiments. ALENEX 2002. Lecture Notes in Computer Science, vol 2409. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45643-0_14
Download citation
DOI: https://doi.org/10.1007/3-540-45643-0_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43977-6
Online ISBN: 978-3-540-45643-8
eBook Packages: Springer Book Archive