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.
Similar content being viewed by others
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