Abstract
Indexing moving objects usually involves a great amount of updates, caused by objects reporting their current position. In order to keep the present and past positions of the objects in secondary memory, each update introduces an I/O and this process is sometimes creating a bottleneck. In this paper we deal with the problem of minimizing the number of I/Os in such a way that queries concerning the present and past positions of the objects can be answered efficiently. In particular we propose a new approach that achieves an asymptotically optimal number of I/Os for performing the necessary updates. The approach is based on the assumption that the primary memory suffices for storing the current positions of the objects.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, A., Vitter, S.J.: The input/output complexity of sorting and related problems. Communications of the ACM 31(9), 1116–1127 (1988)
Becker, B., Gschwind, S., Ohler, T., Seeger, B., Widmayer, P.: An asymptotically optimal multiversion B-tree. The VLDB Journal 5(4), 264–275 (1996)
Cheng, R., Xia, Y., Prabhakar, S., Shah, R.: Change Tolerant Indexing for Constantly Evolving Data. In: ICDE, pp. 391–402. IEEE Computer Society Press, Tokyo (2005)
Kwon, D., Lee, J.S., Lee, S.: Indexing the current positions of moving objects using the lazy update Rtree. In: MDM, pp. 113–120. IEEE Computer Society, Singapore (2002)
Lagogiannis, G., Lorentzos, N.: Partially Persistent B-trees with Constant Worst Case Update Time. Technical report 184, Informatics Laboratory, Department of Science, Agricultural University of Athens (May 2010)
Lagogiannis, G., Lorentzos, N., Sideridis, A.B.: Indexing moving objects: A real time approach. Technical report 186, Informatics Laboratory, Department of Science, Agricultural University of Athens (July 2010)
Lee, L.M., Hsu, W., Jensen, S.C., Cui, B., Teo, L.K.: Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In: VLDB, Berlin, pp. 608–619 (2003)
Saltenis, S., Jensen, S.C.: Main memory operation buffering for efficient R-tree update. In: VLDB, pp. 591–602. ACM, Vienna (2007)
Tung, H., Ryu, K.: One update for all moving objects at a timestamp. In: CIT, p. 6. IEEE Computer Society, Seoul (2006)
Varman, P., Verma, R.: An Efficient Multiversion Access Structure. IEEE Transactions on Knowledge and Data Engineering 9(3), 391–409 (1997)
Xiong, X., Aref, G.W.: R-trees with Update Memos. In: ICDE, pp. 22–22. IEEE Computer Society, Atlanta (2006)
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
Lagogiannis, G., Lorentzos, N., Sideridis, A.B. (2010). Indexing Moving Objects: A Real Time Approach. In: Lytras, M.D., Ordonez De Pablos, P., Ziderman, A., Roulstone, A., Maurer, H., Imber, J.B. (eds) Knowledge Management, Information Systems, E-Learning, and Sustainability Research. WSKS 2010. Communications in Computer and Information Science, vol 111. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16318-0_51
Download citation
DOI: https://doi.org/10.1007/978-3-642-16318-0_51
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16317-3
Online ISBN: 978-3-642-16318-0
eBook Packages: Computer ScienceComputer Science (R0)