• Database and Knowledge-Based Systems • Previous Articles     Next Articles

Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies

Nan Chen, Li-Dan Shou*, Gang Chen, and Jin-Xiang Dong   

  1. College of Computer Science, Zhejiang University, Hangzhou 310027, China
  • Received:2007-06-27 Revised:2008-05-13 Online:2008-11-10 Published:2008-11-10

In recent years, management of moving objects has emerged as an active topic of spatial access methods. Various data structures (indexes) have been proposed to handle queries of moving points, for example, the well-known B$^x$-tree uses a novel mapping mechanism to reduce the index update costs. However, almost all the existing indexes for predictive queries are not applicable in certain circumstances when the update frequencies of moving objects become highly variable and when the system needs to balance the performance of updates and queries. In this paper, we introduce two kinds of novel indexes, named B$^y$-tree and $\al {\rm B}^y$-tree. By associating a {\em prediction life period} with every moving object, the proposed indexes are applicable in the environments with highly variable update frequencies. In addition, the $\al {\rm B}^y$-tree can balance the performance of updates and queries depending on a balance parameter. Experimental results show that the B$^y$-tree and $\al {\rm B}^y$-tree outperform the B$^x$-tree in various conditions.

Key words: deductive language; embroidery pattern; operators of space relation;

[1] Christian S Jensen, Dalia Tiesyte, Nerius Tradisauskas. Robust B$^+$-tree-based indexing of moving objects. In {\it Proc. MDM}, Nara, Japan, 2006, p.12.
[2]} Antonin Guttman. R-trees: A dynamic index structure for spatial searching. In {\it Proc. SIGMOD Conference}, Boston, MA, USA, 1984, pp.47--57.
[3]} Simonas Saltenis, Christian S Jensen, Scott T Leutenegger, Mario A Lopez. Indexing the positions of continuously moving objects. In {\it Proc. SIGMOD Conference}, Dallas, TX, USA, 2000, pp.331--342.
[4]} Simonas Saltenis, Christian S Jensen. Indexing of moving objects for location-based services. In {\it Proc. ICDE}, San Jose, CA, USA, 2002, pp.463--472.
[5]} Yufei Tao, Dimitris Papadias, Jimeng Sun. The TPR*-tree: An optimized spatio-temporal access method for predictive queries. In {\it Proc. VLDB}, Berlin, Germany, 2003, pp.790--801.
[6]} Jignesh M Patel, Yun Chen, V Prasad Chakka. STRIPES: An efficient index for predicted trajectories. In {\it Proc. SIGMOD Conference}, Paris, France, 2004, pp.637--646.
[7]} Hanan Samet. The quadtree and related hierarchical data structures. {\it ACM Comput. Surv}., 1984, 16(2): 187--260.
[8]} Christian S Jensen, Dan Lin, Beng Chin Ooi. Query and update efficient B$^+$-tree based indexing of moving objects. In {\it Proc. VLDB}, Toronto, Ontario, Canada, 2004, pp.768--779.
[9]} Mohamed F Mokbel, Thanaa M Ghanem, Walid G Aref. Spatio-temporal access methods. {\it IEEE Data Eng. Bull}., 2003, 26(2): 40--49.
[10]} Bin Lin, Hoda Mokhtar, Rafael Pelaez-Aguilera, Jianwen Su. Querying moving objects with uncertainty. In {\it Proc. Vehicular Technology Conference}, Orlando, FL, USA, 2003, pp.2783--2787.
[11]} Ji-Dong Chen, Xiao-Feng Meng. Indexing future trajectories of moving objects in a constrained network. {\it Journal of Computer Science and Technology}, 2007, 22(2): 245--251.
[12]} Yufei Tao, Jun Zhang, Dimitris Papadias, Nikos Mamoulis. An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces. {\it IEEE Trans. Knowl. Data Eng}., 2004, 16(10): 1169--1184.
[13]} Mong-Li Lee, Wynne Hsu, Christian S. Jensen, Bin Cui, Keng Lik Teo. Supporting frequent updates in R-trees: A bottom-up approach. In {\it Proc. VLDB}, Berlin, Germany, 2003, pp.608--619.
[14]} Xiaopeng Xiong, Walid G Aref. R-trees with update memos. In {\it Proc. ICDE}, Atlanta, Georgia, USA, 2006, p.22.
[15]} Goetz Graefe. B-tree indexes for high update rates. {\it SIGMOD Record}, 2006, 35(1): 39--44.
[16]} Bongki Moon, H V Jagadish, Christos Faloutsos, Joel H Saltz. Analysis of the clustering properties of the Hilbert space-filling curve. {\it IEEE Trans. Knowl. Data Eng}., 2001, 13(1): 124--141.
[17]} V Srinivasan, Michael J Carey. Performance of B-tree concurrency algorithms. In {\it Proc. SIGMOD Conference}, Denver, CO, USA, 1991, pp.416--425.
[1] MENG Bo; GUO Lei; CHEN Shifu;. DPAL: Deductive Language for Embroidery Pattern Assembling [J]. , 2000, 15(6): 625-628.
[2] MENG Bo(孟波),GUO Lei(郭磊)and CHEN Shifu(陈世福). DPAL:Deductive Language for Embroidery Pattern Assembling [J]. , 2000, 15(6): 0-0.
Full text



[1] Xu Zhiming;. Discrete Interpolation Surface[J]. , 1990, 5(4): 329 -332 .
[2] Hock C. Chan;. Translational Semantics for a Conceptual Level Query Language[J]. , 1995, 10(2): 175 -187 .
[3] Run-Yao Duan, Zheng-Feng Ji, Yuan Feng, and Ming-Sheng Ying. Some Issues in Quantum Information Theory[J]. , 2006, 21(5): 776 -789 .
[4] Da Wang, Yu Hu, Hua-Wei Li, and Xiao-Wei Li. Design-for-Testability Features and Test Implementation of a Giga Hertz General Purpose Microprocessor[J]. , 2008, 23(6 ): 1037 -1046 .
[5] Chong Long(龙 翀), Min-Lie Huang(黄民烈), Xiao-Yan Zhu(朱小燕), Member, CCF and Ming Li(李 明), Fellow, ACM, IEEE. A New Approach for Multi-Document Update Summarization[J]. , 2010, 25(4): 739 -749 .
[6] Leonardo Liao (廖鑫鹏), Yong-Qiang Wu (吴永强), and Chong-Zhao Han (韩崇昭). Hierarchical Polytope ARTMAP for Supervised Learning[J]. , 2010, 25(5): 1071 -1082 .
[7] Jun Wang (王珺), Yong-Tao Cao (曹涌涛), Jun-Yuan Xie (谢俊元), Member, CCF, and Shi-Fu Chen (陈世福). Energy Efficient Backoff Hierarchical Clustering Algorithms for Multi-Hop Wireless Sensor Networks[J]. , 2011, 26(2): 283 -291 .
[8] Jehad Al Dallal and Kassem A. Saleh. Synthesizing Distributed Protocol Specifications from a UML State Machine Modeled Service Specification[J]. , 2012, 27(6): 1150 -1168 .
[9] Wen-Yu Li, Xiang Zhang, Shu-Cong Jia, Xin-Yu Gu, Lin Zhang, Xiao-Yu Duan, and Jia-Ru Lin. A Novel Dynamic Adjusting Algorithm for Load Balancing and Handover Co-Optimization in LTE SON[J]. , 2013, 28(3): 437 -444 .
[10] Jinho Kim, Sang-Wook Kim, Sanghyun Park, Haixun Wang. Preface[J]. , 2013, 28(4): 583 -584 .

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