ST2B-tree: a self-tunable spatio-temporal b+-tree index for moving objects

ABSTRACT

In a moving objects database (MOD) the dataset and the workload change frequently. As the locations of objects change in space and time, the data distribution also changes and the answer for a same query over the same region may vary widely over time. As a result, traditional static indexes are not able to perform well and it is critical to develop self-tuning indexes that can be reconfigured automatically based on the state of the system. Towards this goal we propose the ST²B-tree, a Self-Tunable Spatio-Temporal B⁺-Tree index for MODs, which is amenable to tuning. Frequent updates to its subtrees allows rebuilding (tuning) a subtree using a different set of reference points and different grid size without significant overhead. We also present an online tuning framework for the ST²B-tree, where the tuning is conducted online and automatically without human intervention, also not interfering with regular functions of the MOD. Our extensive experiments show that the self-tuning process minimizes the effectiveness degradation of the index caused by workload changes at the cost of virtually no overhead.

REFERENCES

• 1: SpADE: A SPatio-temporal Autonomic Database Engine forlocation-aware services. http://www.comp.nus.edu.sg/~spade/.
• 2: TPR*-tree. http://www.rtreeportal.org/code.html.
• 3: Mihael Ankerst , Markus M. Breunig , Hans-Peter Kriegel , Jörg Sander, OPTICS: ordering points to identify the clustering structure, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.49-60, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Surajit Chaudhuri , Vivek R. Narasayya, An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server, Proceedings of the 23rd International Conference on Very Large Data Bases, p.146-155, August 25-29, 1997
• 5: S. Chen, B. C. Ooi, K. L. Tan, and M. A. Nascimento. Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects. Technical Report, 2007.
• 6: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In KDD, pages 226--231, 1996.
• 7: Shuqiao Guo , Zhiyong Huang , H. V. Jagadish , Beng Chin Ooi , Zhenjie Zhang, Relaxed space bounding for moving objects: a case for the buddy tree, ACM SIGMOD Record, v.35 n.4, p.24-29, December 2006 [doi>10.1145/1228268.1228272]
• 8: Christian S. Jensen , Dan Lin , Beng Chin Ooi, Query and update efficient B⁺-tree based indexing of moving objects, Proceedings of the Thirtieth international conference on Very large data bases, p.768-779, August 31-September 03, 2004, Toronto, Canada
• 9: Christian S. Jensen , Dalia Tie!sytye , Nerius Tradi!sauskas, Robust B+-Tree-Based Indexing of Moving Objects, Proceedings of the 7th International Conference on Mobile Data Management, p.12, May 10-12, 2006 [doi>10.1109/MDM.2006.135]
• 10: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 11: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 12: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 13: Kyriakos Mouratidis , Dimitris Papadias , Marios Hadjieleftheriou, Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066230]
• 14: Jignesh M. Patel , Yun Chen , V. Prasad Chakka, STRIPES: an efficient index for predicted trajectories, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007639]
• 15: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 16: Bernhard Seeger , Hans-Peter Kriegel, The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems, Proceedings of the 16th International Conference on Very Large Data Bases, p.590-601, August 13-16, 1990
• 17: Yufei Tao , Dimitris Papadias , Jimeng Sun, The TPR*-tree: an optimized spatio-temporal access method for predictive queries, Proceedings of the 29th international conference on Very large data bases, p.790-801, September 09-12, 2003, Berlin, Germany
• 18: Yufei Tao , Jun Zhang , Dimitris Papadias , Nikos Mamoulis, An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1169-1184, October 2004 [doi>10.1109/TKDE.2004.48]
• 19: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering, p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 20: Man Lung Yiu , Yufei Tao , Nikos Mamoulis, The Bdual-Tree: indexing moving objects by space filling curves in the dual space, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.379-400, May 2008 [doi>10.1007/s00778-006-0013-2]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
data distribution, index tuning, location-based services, moving object indexing, self-tuning