Abstract
The problem of frequently updating multi-dimensional indexes arises in many location-dependent applications. While the R-tree and its variants are the dominant choices for indexing multi-dimensional objects, the R-tree exhibits inferior performance in the presence of frequent updates. In this paper, we present an R-tree variant, termed the RUM-tree (which stands for R-tree with update memo) that reduces the cost of object updates. The RUM-tree processes updates in a memo-based approach that avoids disk accesses for purging old entries during an update process. Therefore, the cost of an update operation in the RUM-tree is reduced to the cost of only an insert operation. The removal of old object entries is carried out by a garbage cleaner inside the RUM-tree. In this paper, we present the details of the RUM-tree and study its properties. We also address the issues of crash recovery and concurrency control for the RUM-tree. Theoretical analysis and comprehensive experimental evaluation demonstrate that the RUM-tree outperforms other R-tree variants by up to one order of magnitude in scenarios with frequent updates.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Antonin Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: SIGMOD (1984)
Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-tree: an efficient and robust access method for points and rectangles. In: SIGMOD (1990)
Brinkhoff, T.: A framework for generating network-based moving objects. GeoInformatica 6(2), (2002)
Chakka, P.V., Everspaugh, A., Patel, J.M.: Indexing large trajectory data sets with SETI. In: Proceeding of the Conference on Innovative Data Systems Research, CIDR (2003)
Chakrabarti, K., Mehrotra S.: Dynamic granular locking approach to phantom protection in r-trees. In: ICDE (1998)
Cheng, R., Xia, Y., Prabhakar, S., Shah, R.: Change tolerant indexing for constantly evolving data. In: ICDE (2005)
Hadjieleftheriou, M., Kollios G., Tsotras, V.J., Gunopulos, D.: Efficient indexing of spatiotemporal objects. In: EDBT, pp. 251–268, Prague, March (2002)
Kalashnikov D.V., Prabhakar S., Hambrusch S.E.: Main memory evaluation of monitoring queries over moving objects. Distrib. Parallel Databases 15(2), 117–135 (2004)
Kamel, I., Faloutsos, C.: Hilbert R-tree: an improved R-tree using fractals. In: VLDB, pp. 500–509 (1994)
Kim, K., Cha, S.K., Kwon, K.: Optimizing multidimensional index trees for main memory access. In: SIGMOD (2001)
Kollios, G., Gunopulos, D., Tsotras, V.J.: On indexing mobile objects. In: PODS (1999)
Kwon, D., Lee, S., Lee, S.: Indexing the current positions of moving objects using the lazy update R-tree. In: Mobile Data Management, MDM (2002)
Lee, M.-L., Hsu, W., Jensen, C.S., Teo, K.L.: Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. In VLDB, (2003)
Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A.N., Theodoridis, Y.: R-trees have grown everywhere. In: Technical Report, Available at http://citeseer.ist.psu.edu/706599.html (2003)
Nascimento, M.A., Silva, J.R.O.: Towards historical R-trees. In: Proceeding of the ACM Symposium on Applied Computing, SAC, pp. 235–240, February (1998)
Pfoser, D., Jensen, C.S., Theodoridis, Y.: Novel approaches in query processing for moving object trajectories. In: VLDB, pp. 395–406, September (2000)
Porkaew, K., Lazaridis, I., Mehrotra, S.: Querying mobile objects in spatio-temporal databases. In: SSTD, pp. 59–78, Redondo Beach, July (2001)
Prabhakar S., Xia Y., Kalashnikov D.V., Aref W.G., Hambrusch S.E.: Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. IEEE Trans. Comput. 51(10), 1124–1140 (2002)
Procopiuc, C.M., Agarwal, P.K., Har-Peled, S.: STAR-tree: an efficient self-adjusting index for moving objects. In: Proceeding of the Workshop on Algorithm Engineering and Experimentation, ALENEX, pp. 178–193, January (2002)
Roussopoulos, N., Leifker, D.: Direct spatial search on pictorial databases using packed r-trees. In: SIGMOD, pp. 17–31 (1985)
Saltenis, S., Jensen, C.S.: Indexing of moving objects for location-based services. In: ICDE (2002)
Saltenis S., Jensen C.S.: Indexing of now-relative spatio-bitemporal data. VLDB J. 11(1), 1–16 (2002)
Saltenis, S., Jensen, C.S., Leutenegger, S.T., Lopez, M.A.: Indexing the positions of continuously moving objects. In: SIGMOD (2000)
Sellis, T.K.: Nick Roussopoulos, and Christos Faloutsos. The r+-tree: a dynamic index for multi-dimensional objects. In: VLDB, pp. 507–518 (1987)
Tao, Y., Papadias, D.: Efficient historical R-trees. In: SSDBM, pp. 223–232, July (2001)
Tao, Y., Papadias, D.: MV3R-tree: a spatio-temporal access method for timestamp and interval queries. In: VLDB (2001)
Tao, Y., Papadias, D., Sun, J.: The TPR*-tree: an optimized spatio-temporal access method for predictive queries. In: VLDB (2003)
Theodoridis, Y., Vazirgiannis, M., Sellis, T.: Spatio-temporal indexing for large multimedia applications. In: Proceedings of the IEEE Conference on Multimedia Computing and Systems, ICMCS, June (1996)
Xiong, X., Aref, W.G.: R-trees with update memos. In: ICDE (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Silva, Y.N., Xiong, X. & Aref, W.G. The RUM-tree: supporting frequent updates in R-trees using memos. The VLDB Journal 18, 719–738 (2009). https://doi.org/10.1007/s00778-008-0120-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-008-0120-3