Synonyms
Definition
One of the most influential access methods in the area of Spatial Data Management is the R-tree structure proposed by Guttman in 1984. It is a hierarchical data structure based on B+-trees, used for the dynamic organization of a set of d-dimensional geometric objects. The original R-tree was designed for efficiently retrieving geometric objects contained within a given query range. Every object in the R-tree is represented by a minimum bounding d-dimensional rectangle (for simplicity, MBRs in the sequel). Data objects are grouped into larger MBRs forming the leaf nodes of the tree. Leaf nodes are grouped into larger internal nodes. The process continues recursively until the last group of nodes that form the root of the tree. The root represents an MBR that encloses all objects and nodes indexed by the tree, and each node corresponds to the MBR that bounds its children (cf. Fig. 1). A range query can be answered efficiently by traversing the tree starting...
This is a preview of subscription content, log in via an institution to check access.
References
Ang C-H, Tan TC (1997) New linear node splitting algorithm for r-trees. In: Proceedings of symposium on advances in spatial databases (SSD), Berlin, 15–18 July 1997, pp 339–349
Beckmann N, Kriegel H, Schneider R, Seeger B (1990) The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of ACM management of data (SIGMOD), Atlantic City, 23–25 May 1990, pp 220–231
Brakatsoulas S, Pfoser D, Theodoridis Y (2002) Revisiting r-tree construction principles. In: Proceedings of the East European conference on advances in databases and information systems, Bratislava, 8–11 Sept 2002, pp 149–162
Driscoll JR, Sarnak N, Sleator DD, Tarjan RE (1989) Making data structures persistent. J Comput Syst Sci 38(1):86–124
Faloutsos C, Kamel I (1994) Beyond uniformity and independence: analysis of r-trees using the concept of fractal dimension. In: Proceedings of ACM symposium on principles of database systems (PODS), Minneapolis, 24–26 May 1994, pp 4–13
Faloutsos C, Sellis T, Roussopoulos N (1987) Analysis of object oriented spatial access methods. SIGMOD Rec 16(3):426–439
Garcia YJ, Lopez MA, Leutenegger ST (1998) On optimal node splitting for r-trees. In: Proceedings of very large data bases (VLDB), New York, 24–27 Aug 1998, pp 334–344
Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM management of data (SIGMOD), Boston, 18–21 June 1984, pp 47–57
Hadjieleftheriou M, Hoel E, Tsotras VJ (2004) Sail: a library for efficient application integration of spatial indices. In: Proceedings of scientific and statistical database management (SSDBM), Santorini Island, 21–23 2004, pp 135–138
Hadjieleftheriou M, Kollios G, Tsotras VJ, Gunopulos D (2002) Efficient indexing of spatiotemporal objects. In: Proceedings of extending database technology (EDBT), Prague, 24–28 Mar 2002, pp 251–268
Huang PW, Lin PL, Lin HY (2001) Optimizing storage utilization in r-tree dynamic index structure for spatial databases. J Syst Softw 55(3):291–299
Kamel I, Faloutsos C (1993) On packing r-trees. In: Proceedings of conference on information and knowledge management (CIKM), Washington, DC, 1–5 Nov 1993, pp 490–499
Kamel I, Faloutsos C (1994) Hilbert r-tree: an improved r-tree using fractals. In: Proceedings of very large data bases (VLDB), Santiago de Chile, 12–15 Sept 1994, pp 500–509
Kollios G, Tsotras VJ, Gunopulos D, Delis A, Hadjieleftheriou M (2001) Indexing animated objects using spatiotemporal access methods. IEEE Trans Knowl Data Eng (TKDE) 13(5):758–777
Kolovson C, Stonebraker M (1991) Segment indexes: dynamic indexing techniques for multi-dimensional interval data. In: Proceedings of ACM management of data (SIGMOD), Denver, 29–31 May 1991, pp 138–147
Kumar A, Tsotras VJ, Faloutsos C (1998) Designing access methods for bitemporal databases. IEEE Trans Knowl Data Eng (TKDE) 10(1):1–20
Leutenegger ST, Edgington JM, Lopez MA (1997) Str: a simple and efficient algorithm for r-tree packing. In: Proceedings of international conference on data engineering (ICDE), Birmingham, 7–11 Apr 1997, pp 497–506
Manolopoulos Y, Nanopoulos A, Papadopoulos AN, Theodoridis Y (2005) Rtrees: theory and applications. Springer
Nanopoulos A, Vassilakopoulos M, Manolopoulos Y (2003) Performance evaluation of lazy deletion methods in r-trees. GeoInformatica 7(4):337–354
Roussopoulos N, Leifker D (1985) Direct spatial search on pictorial databases using packed r-trees. SIGMOD Rec 14(4):17–31
Saltenis S, Jensen CS, Leutenegger ST, Lopez MA (2000) Indexing the positions of continuously moving objects. SIGMOD Rec 29(2):331–342
Schreck T, Chen Z (2000) Branch grafting method for r-tree implementation. J Syst Softw 53(1):83–93
Sellis T, Roussopoulos N, Faloutsos C (1987) The r+-tree: a dynamic index for multi-dimensional objects. In: Proceedings of very large data bases (VLDB), Brighton, pp 507–518
Tao Y, Papadias D (2001) MV3R-Tree: a spatio-temporal access method for timestamp and interval queries. In: Proceedings of very large data bases (VLDB), Roma, pp 431–440
Theodoridis Y (2003) The R-tree-portal
Theodoridis Y, Sellis T (1996) A model for the prediction of r-tree performance. In: Proceedings of ACM symposium on principles of database systems (PODS), Montreal, pp 161–171
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this entry
Cite this entry
Hadjieleftheriou, M., Manolopoulos, Y., Theodoridis, Y., Tsotras, V.J. (2016). R-Trees: A Dynamic Index Structure for Spatial Searching. In: Shekhar, S., Xiong, H., Zhou, X. (eds) Encyclopedia of GIS. Springer, Cham. https://doi.org/10.1007/978-3-319-23519-6_1151-2
Download citation
DOI: https://doi.org/10.1007/978-3-319-23519-6_1151-2
Received:
Accepted:
Published:
Publisher Name: Springer, Cham
Online ISBN: 978-3-319-23519-6
eBook Packages: Springer Reference Computer SciencesReference Module Computer Science and Engineering