We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 24 Issue 6
November  2009
Turn off MathJax
Article Contents
Abstract
References
Utku Kalay, Oya Kalipsiz. A Comparison Study of Moving Object Index Structures[J]. Journal of Computer Science and Technology, 2009, 24(6): 1098-1108.
Citation: Utku Kalay, Oya Kalipsiz. A Comparison Study of Moving Object Index Structures[J]. Journal of Computer Science and Technology, 2009, 24(6): 1098-1108.
shu

A Comparison Study of Moving Object Index Structures

  • Computer Engineering Department, Yildiz Technical University, Besiktas, Istanbul, 34349, Turkey

More Information
  • Author Bio:

    Utku Kalay received the B.S. degree in electrical engineeringfrom Istanbul Technical University in 1997 and M.S. degree in computerscience from University of Southern California, Los Angeles in 2000. Hereceived the Ph.D. degree in computer engineering from Yildiz TechnicalUniversity. He is currently working as an associate professor andlecturer. His main research interests are robust index organizations,moving object databases and information retrieval.

    Oya Kalipsiz received her M.S. degree in computer engineeringfrom Istanbul Technical University in 1984. She received her Ph.D.degree from Istanbul University in 1989 with a study on HospitalInformation Systems. She is currently working as the head of ComputerEngineering Department of Yildiz Technical University. Her mainresearch interests are software engineering, database systems, datamining, system analysis, and management information systems.

  • Received Date: September 09, 2008
  • Revised Date: August 16, 2009
  • Published Date: November 04, 2009
    Abstract
  • 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.
    • FullText(HTML)
    • References (20)
  • [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.
    • Relative Articles
  • Supplements (0)

Catalog

    Get Citation
    XML
    Article views (31) PDF downloads (1908) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return