Abstract
Self-tuning database is a general paradigm for the future development of database systems. However, in moving object database, a vibrant and dynamic research area of the database community, the need for self-tuning has so far been overlooked. None of the existing spatio-temporal indexes can maintain high performance if the proportion of query and update operations varies significantly in the applications. We study the self-tuning indexing techniques which balance the query and update performances for optimal overall performance in moving object databases. In this paper, we propose a self-tuning framework which relies on a novel moving object index named \(\textrm{B}^s\)-tree. This framework is able to optimize its own overall performance by adapting to the workload online without interrupting the indexing service. We present various algorithms for the \(\textrm{B}^s\)-tree and the tuning techniques. Our extensive experiments show that the framework is effective, and the \(\textrm{B}^s\)-tree outperforms the existing indexes under different circumstances.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In: SIGMOD Conference, Atlantic City, NJ, May 1990, pp. 322–331 (1990)
Benetis, R., Jensen, C.S., Karciauskas, G., Saltenis, S.: Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. VLDB J. 15(3), 229–249 (2006)
Chaudhuri, S., Narasayya, V.R.: An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server. In: VLDB, Athens, Greece, August 1997, pp. 146–155 (1997)
Chen, N., Shou, L.-D., Chen, G., Dong, J.-X.: Adaptive Indexing of Moving Objects with Highly Variable Update Frequencies. Journal of Computer Science and Technology (JCST) 23(6), 998–1014 (2008)
Chen, S., Ooi, B.C., Tan, K.-L., Nascimento, M.A.: S2TB-Tree: A Self-Tunable Spatio-Temporal B+-Tree Index for Moving Objects. In: SIGMOD Conference, Vancouver, BC, Canada, June 2008, pp. 29–42 (2008)
Guo, S., Huang, Z., Jagadish, H.V., Ooi, B.C., Zhang, Z.: Relaxed Space Bounding for Moving Objects: A Case for the Buddy Tree. SIGMOD Record (SIGMOD) 35(4), 24–29 (2006)
Guttman, A.: R-Trees: A Dynamic Index Structure for Spatial Searching. In: SIGMOD Conference, Boston, Massachusetts, June 1984, pp. 47–57 (1984)
Jensen, C.S., Lin, D., Ooi, B.C.: Query and Update Efficient B+-Tree Based Indexing of Moving Objects. In: VLDB, Toronto, Ontario, Canada, August 2004, pp. 768–779 (2004)
Saltenis, S., Jensen, C.S., Leutenegger, S.T., Lopez, M.A.: Indexing the Positions of Continuously Moving Objects. In: SIGMOD Conference, Dallas, Texas, USA, May 2000, pp. 331–342 (2000)
Srinivasan, V., Michael, Carey, J.: Performance of B-Tree Concurrency Algorithmss. In: SIGMOD Conference, Denver, Colorado, May 1991, pp. 416–425 (1991)
Tao, Y., Papadias, D., Sun, J.: The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries. In: VLDB, Berlin, Germany, September 2003, pp. 790–801 (2003)
Tao, Y., Zhang, J., Papadias, D., Mamoulis, N.: An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces. IEEE Trans. Knowl. Data Eng. (TKDE) 16(10), 1169–1184 (2004)
Yiu, M.L., Tao, Y., Mamoulis, N.: The Bdual-Tree: indexing moving objects by space filling curves in the dual space. VLDB J. (VLDB) 17(3), 379–400 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, N., Shou, L., Chen, G., Chen, K., Gao, Y. (2010). \(\textrm{B}^s\)-tree: A Self-tuning Index of Moving Objects. In: Kitagawa, H., Ishikawa, Y., Li, Q., Watanabe, C. (eds) Database Systems for Advanced Applications. DASFAA 2010. Lecture Notes in Computer Science, vol 5982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12098-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-12098-5_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12097-8
Online ISBN: 978-3-642-12098-5
eBook Packages: Computer ScienceComputer Science (R0)