Abstract
Developing efficient index structures is an important issue for moving object database. Currently, most indexing methods of moving objects are focused on the past position, or on the present and future one. In this paper, we propose a novel indexing method, called HTPR*-tree (History Time-Parameterized R-tree), which not only supports predictive queries but also partial history ones involved from the most recent update instant of each object to the last update time. Based on the TPR*-tree, our HTPR*-tree adds creation or update time of moving objects to leaf node entries. This index is the foundation of indexing the past, present and future positions of moving objects. In order to improve the update performance, we present a bottom-up update strategy for the HTPR*-tree by supplementing three auxiliary structures which include hash index, bit vector, and direct access table. Experimental results show that the update performance of the HTPR*-tree is better than that of the TD_HTPR*- and TPR*-tree. Moreover, the HTPR*-tree can support partial history queries compared with TPR*-tree although the predictive query performance is a bit less.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Saltenis, S., Jensen, C.S., Leutenegger, S.T., Lopez, M.A.: Indexing the Positions of Continuously Moving Objects. In: ACM SIGMOD, pp. 331–342 (2000)
Tao, Y., Papadias, D., Sun, J.: The TPR*-Tree: An Optimized spatiotemporal Access Method for Predictive Queries. In: VLDB, pp. 790–801 (2003)
Lee, M., Hsu, W., Jensen, C., et al.: Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In: VLDB, pp. 608–619 (2003)
Pfoser, D., Jensen, C.S., Theodoridis, Y.: Novel Approaches to the Indexing of Moving Object Trajectories. In: VLDB, pp. 395–406 (2000)
Theodoridis, Y., Vazirgiannis, M., Sellis, T.: Spatio-temporal Indexing for Large Multimedia Applications. In: Conf. on Multimedia Computing and Systems, pp. 441–448 (1996)
Nascimento, M.A., Silva, J.R.O.: Towards Historical R-trees. In: Proc. of the ACM Symposium on Applied Computing, pp. 235–240 (1998)
Tayeb, J., Ulusoy, O., Wolfson, O.: A Quadtree-Based Dynamic Attribute Indexing Method. The Computer Journal 41(3), 185–200 (1998)
Jignesh, M., Yun, P., Chen, V., Chakka, P.: TRIPES: An Efficient Index for Predicted Trajectories. In: ACM SIGMOD, pp. 637–646 (2004)
Liao, W., Tang, G.F., Jing, N., Zhong, Z.-N.: Hybrid Indexing of Moving Objects Based on Velocity Distribution. Chinese Journal of Computers 30(4), 661–671 (2007)
Jensen, C.S., Lin, D., Ooi, B.C.: Query and Update Efficient B+-Tree Based Indexing of Moving Objects. In: VLDB, pp. 768–779 (2004)
Chen, S., Ooi, B.C., Tan, K.L., et al.: ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects. In: ACM SIGMOD, pp. 29–42 (2008)
Chen, N., Shou, L.D., Chen, G., et al.: Bs-tree: A Self-tuning Index of Moving Objects. In: Kitagawa, H., Ishikawa, Y., Li, Q., Watanabe, C. (eds.) DASFAA 2010. LNCS, vol. 5982, pp. 1–16. Springer, Heidelberg (2010)
Pelanis, M., Saltenis, S., Jensen, C.S.: Indexing the Past, Present and Anticipated Future Positions of Moving Objects. In: ACM TODS, pp. 255–298 (2006)
Raptopoulou, K., Vassilakopoulos, M., Manolopoulos, Y.: Efficient processing of past-future spatiotemporal queries. In: Proc. of the ACM Symposium on Applied Computing, pp. 68–72 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fang, Y., Cao, J., Wang, J., Peng, Y., Song, W. (2012). HTPR*-Tree: An Efficient Index for Moving Objects to Support Predictive Query and Partial History Query. In: Wang, L., Jiang, J., Lu, J., Hong, L., Liu, B. (eds) Web-Age Information Management. WAIM 2011. Lecture Notes in Computer Science, vol 7142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28635-3_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-28635-3_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28634-6
Online ISBN: 978-3-642-28635-3
eBook Packages: Computer ScienceComputer Science (R0)