›› 2009, Vol. 24 ›› Issue (6): 1098-1108.

• Distributed Computing and Systems • Previous Articles     Next Articles

A Comparison Study of Moving Object Index Structures

Utku Kalay and Oya Kalipsiz   

  1. Computer Engineering Department, Yildiz Technical University, Besiktas, Istanbul, 34349, Turkey
  • Received:2008-09-10 Revised:2009-08-17 Online:2009-11-05 Published:2009-11-05
  • About author:
    Utku Kalay received the B.S. degree in electrical engineering from Istanbul Technical University in 1997 and M.S. degree in computer science from University of Southern California, Los Angeles in 2000. He received the Ph.D. degree in computer engineering from Yildiz Technical University. He is currently working as an associate professor and lecturer. His main research interests are robust index organizations, moving object databases and information retrieval.
    Oya Kalipsiz received her M.S. degree in computer engineering from Istanbul Technical University in 1984. She received her Ph.D. degree from Istanbul University in 1989 with a study on Hospital Information Systems. She is currently working as the head of Computer Engineering Department of Yildiz Technical University. Her main research interests are software engineering, database systems, data mining, system analysis, and management information systems.

The task of selecting the most appropriate method for indexing the data according to application requires a careful comparison study of indices of interests. In particular, we consider object movements by tracing their trajectories within a predefined road network. MV3DR-tree and 3DR-tree constitute our first group indexing the objects moving in free movement scenarios. Besides, Mapping and MON-tree are the second group indexing the locations of objects moving over a network of road. Those access methods mainly organize a group of R-tree in order to index the underlying road network and the object movements. Our goal in this study is to evaluate existing proposals under fair circumstances with respect to storage consumption and spatio-temporal query execution performance. In our comparisons, we discuss the structure's sensibility to query's spatial and/or temporal extent as well as the tradeoff arising between two groups in terms of reliability and disk access performance. We believe that revealing the vulnerabilities of the selected structures, especially Mapping and MON-tree motivates us to design more robust organizations.

[1] Guttman A. R-trees: A dynamic index structure for spatial searching. In Proc. the ACM SIGMOD Conference on Management of Data, Boston, USA, June 18–21, 1984, pp.47–57.
[2] Theodoridis Y, Vazirgiannis M, Sellis T. Spatio-temporal indexing for large multimedia applications. In Proc. the 3rd IEEE Conference on Multimedia Computing and Systems (ICMCS 1996), Hiroshima, Japan, June 17–23, 1996, pp.441– 448.
[3] Pfoser D, Jensen C S, Theodoridis Y. Novel approaches to the indexing of moving object trajectories. In Proc. the 26th International Conference on Very Large Databases, Cairo, Egypt, Sept. 10–14, 2000, pp.395–406.
[4] Nascimento M A, Silva J R O. Towards historical R-trees. In Proc. ACM Symposium on Applied Computing (ACMSAC1998), Atlanta, Georgia, Feb. 27–Mar. 1, 1998, pp.235– 240.
[5] Tao Y, Papadias D. MV3DR-tree: A spatiotemporal access method for timestamp and interval queries. In Proc. the 27th International Conference on Very Large Databases, Roma, Italy, Sept. 11–14, 2001, pp. 431–440.
[6] Jensen C S, Pfoser D. Indexing of network constrained moving objects. In Proc. the 11th Int. Symp. Advances in Geographic Information Systems (ACM-GIS 2003), New Orleans, USA, Nov. 7–8, 2003, pp.1–8.
[7] Frentzos E. Indexing objects moving on fixed networks. In Proc. the 8th Int. Symp. Spatial and Temporal Databases (SSTD2003), Santorini Island, Greece, July 24–27, 2003, pp.289–305.
[8] Almeida V T, G¨uting R H. Indexing the trajectories of moving objects in networks. GeoInformatica, 2005, 9(1): 33–60.
[9] Kollios G, Gunopulos D, Tsotras V J. On indexing mobile objects. In Proc. ACM Symp. Principles of Database Systems (PODS 1999), Philadephia, USA, May 31–June 2, 1999, pp.261–272.
[10] Saltenis S, Jensen C S, Leutenegger S T, Lopez M A. Indexing the positions of continuously moving objects. In Proc. the SIGMOD Int. Conf. Management of Data, Dallas, USA, May 16–18, 2000, pp.331–342.
[11] Tao Y, Papadias D, Sun J. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In Proc. the Int. Conf. Very Large Data Bases (VLDB2003), Berlin, Germany, Sept. 9–12, 2003, pp.790–801.
[12] Spatial Index Library (SaIL). http://u-foria.org/marioh/spatialindex/ index.html.
[13] Kamel I, Faloutsos C. Hilbert R-tree: An improved R-tree using fractals. In Proc. the 20th VLDB Conf., Chile, Sept. 12– 15, 1994, pp.500–509.
[14] Kollios G, Gunopulos D, Tsotras V, Delis A, Hadjieleftheriou M. Indexing animated objects using spatiotemporal access methods. IEEE TKDE, 2001, 13(5): 758–777.
[15] Papadias D, Zhang J, Mamoulis N, Tao Y. Query processing in spatial network databases. In Proc. the 29th Int. Conf. Very Large Data Bases (VLDB2003), Berlin, Germany, Sept. 9–12, 2003, pp.802–813.
[16] Wolfson O, Sistla A P, Chamberlain S, Yesha Y. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 1999, 7(3): 257–387.
[17] Ding Z, Zhou X. Location update strategies for networkconstrained moving objects. In Proc. 13th Int. Conference on Database Systems for Advance Applications (DASFAA2008), New Delphi, India, March 19–21, 2008, pp.644–652.
[18] Leutenegger S T, Lopez M A. The effect of buffering on the performance of R-trees. Transaction on Knowledge and Data Engineering, 2000, 12(1): 33–44.
[19] Brinkhoff T. A Robust and self-tuning page-replacement strategy for spatial database systems. In Proc. Conference on Extending Database Technology (EDBT 2002), Prague, Czech Republic, March 25–27, 2002, pp.533–552.
[20] Sacco G M. Index access with a finite buffer. In Proc. the Very Large Data Bases Conf., Athens, Greece, Aug. 25–29, 1997, pp.301–309.

No related articles found!
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved