Editing R-tree (section)

{{Short description|Data structures used in spatial indexing}}
{{About|the data structure|the type of metric space|Real tree}}
{{More citations needed|date=May 2023}}
{{Infobox data structure
|name=R-tree
|type=tree
|invented_by=[[Antonin Guttman]]
|invented_year=1984
|
|space_avg= 
|space_worst= 
|search_avg= O(''log<sub>M</sub>n'')
|search_worst=O(''n'')<ref>[https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf R Tree] cs.sfu.ca</ref>
|insert_avg= 
|insert_worst= O(''n'')
|delete_avg= 
|delete_worst= 
}}
[[Image:R-tree.svg|thumb|400px|right|Simple example of an R-tree for 2D rectangles]]
[[Image:RTree-Visualization-3D.svg|thumb|400px|right|Visualization of an R*-tree for 3D points using [[ELKI]] (the cubes are directory pages)]]

'''R-trees''' are [[tree data structure]]s used for [[spatial index|spatial access methods]], i.e., for indexing multi-dimensional information such as [[Geographic coordinate system|geographical coordinates]], [[rectangle]]s or [[polygon]]s. The R-tree was proposed by Antonin Guttman in 1984<ref name="guttman">{{Cite book | last1 = Guttman | first1 = A. | chapter = R-Trees: A Dynamic Index Structure for Spatial Searching| doi = 10.1145/602259.602266 | title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84 | pages = 47 | year = 1984 | isbn = 978-0897911283 | s2cid = 876601 | chapter-url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf}}</ref> and has found significant use in both theoretical and applied contexts.<ref name="rtree-book">{{cite book|author1=Y. Manolopoulos|author2=A. Nanopoulos|author3=Y. Theodoridis|title=R-Trees: Theory and Applications|url=https://books.google.com/books?id=1mu099DN9UwC&pg=PR5|access-date=8 October 2011|year=2006|publisher=Springer|isbn=978-1-85233-977-7}}</ref> A common real-world usage for an R-tree might be to store spatial objects such as restaurant locations or the polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as "Find all museums within 2 km of my current location", "retrieve all road segments within 2 km of my location" (to display them in a [[navigation system]]) or "find the nearest gas station" (although not taking roads into account). The R-tree can also accelerate [[nearest neighbor search]]<ref>{{Cite conference | doi = 10.1145/223784.223794| chapter = Nearest neighbor queries| title = Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95| pages = 71| year = 1995| last1 = Roussopoulos | first1 = N. | last2 = Kelley | first2 = S. | last3 = Vincent | first3 = F. D. R. | isbn = 0897917316| doi-access = free}}</ref> for various distance metrics, including [[great-circle distance]].<ref name=geodetic>{{Cite conference | doi = 10.1007/978-3-642-40235-7_9| chapter = Geodetic Distance Queries on R-Trees for Indexing Geographic Data| title = Advances in Spatial and Temporal Databases| volume = 8098| pages = 146| series = Lecture Notes in Computer Science| year = 2013| last1 = Schubert | first1 = E. | last2 = Zimek | first2 = A. | last3 = Kriegel | first3 = H. P. | author-link3=Hans-Peter Kriegel| isbn = 978-3-642-40234-0}}</ref>