R-tree
865249
217396602
2008-06-05T21:13:08Z
SmackBot
433328
Date the maintenance tags or general fixes
{{otheruses4|the data structure|the type of metric space|Real tree}}
[[Image:R-tree.jpg|thumb|400px|right|Simple example of an R-tree for 2D rectangles<!--(Note: The labels "R6" and "R7" in the upper image should be switched.)-->]]
'''R-trees''' are [[tree data structure]]s that are similar to [[B-tree]]s, but are used for [[spatial index|spatial access method]]s i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 miles of my current location".
The data structure splits space with hierarchically nested, and possibly overlapping, [[minimum bounding rectangle]]s (MBR, otherwise known as bounding boxes, i.e. "rectangle", what the "R" in R-tree stands for).
Each node of an R-tree has a variable number of entries (up to some pre-defined maximum). Each entry within a non-[[leaf node]] stores two pieces of data: a way of identifying a [[child node]], and the [[bounding box]] of all entries within this child node.
The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that "nearby" elements are placed in the same [[leaf node]] (in particular, a new element will go into the leaf node that requires the least enlargement in its bounding box). Each entry within a leaf node stores two pieces of information; a way of identifying the actual data element (which, alternatively, may be placed directly in the node), and the bounding box of the data element.
Similarly, the searching algorithms (for example; [[intersection (set theory)|intersection]], [[containment]], nearest) use the bounding boxes to decide whether or not to search inside a child node. In this way, most of the nodes in the tree are never "touched" during a search. Like B-trees, this makes R-trees suitable for [[database]]s, where nodes can be paged to memory when needed.
Different algorithms can be used to split nodes when they become too full, resulting in the ''quadratic'' and ''linear'' R-tree sub-types.
R-trees do not historically guarantee good [[worst-case performance]], but generally performed well with real-world data. However, a new algorithm was published in 2004 that defines the Priority R-Tree, which claims to be as efficient as the currently most efficient methods and is at the same time worst-case optimal.
==Variants==
*[[R* tree]]
*[[R+ tree]]
*[[Hilbert R-tree]]
*Priority R-Tree (PR-Tree) - The PR-tree performs similar to the best known R-tree variants on real-life and relatively nicely distributed data, but outperforms them significantly on more extreme data.<ref>Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi: [http://www.win.tue.nl/~mdberg/Papers/prtree.pdf The Priority RTree: A Practically Efficient and WorstCase Optimal RTree]</ref>
==Algorithm==
=== Search ===
The input is a search rectangle (Query box). Searching is quite similar to searching in a [[B-tree]]. The search starts from the root node of the tree. Every internal node contains a set of rectangles and pointers to the corresponding child node and every leaf node contains the rectangles of spatial objects (the pointer to some spatial object can be there). For every rectangle in a node, it has to be decided if it overlaps the search rectangle or not. If yes, the corresponding child node has to be searched also. Searching is done like this in a recursive manner until all overlapping nodes have been traversed. When a leaf node is reached, the contained bounding boxes (rectangles) are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.
=== Insertion ===
To insert an object, the tree is traversed recursively from the root node. All rectangles in the current internal
node are examined. The constraint of least coverage is employed to insert an object, i.e., the box that needs
least enlargement to enclose the new object is selected. In the case where there is more than one rectangle that
meets this criterion, the one with the smallest area is chosen. Inserting continues recursively in the chosen node.
Once a leaf node is reached, a straightforward insertion is made if the leaf node is not full. If the leaf node
is full, it must be split before the insertion is made. A few splitting algorithms have been proposed for good
R-tree performance.
{{Expand-section|date=June 2008}}
=== Bulk-loading ===
* Sort-Tile-Recursive (STR) <ref>Scott T. Leutenegger, Jeffrey M. Edgington and Mario A. Lopez: [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=4D62F569DDC2B520D1658983F40AC9DC?doi=10.1.1.106.4996&rep=rep1&type=pdf STR: A Simple and Efficient Algorithm for R-Tree Packing]</ref>
* Packed [[Hilbert R-tree|Hilbert R-Tree]] - Uses the Hilbert value of the center of a rectangle to sort the leaf nodes and recursively builds the tree.
* Nearest-X - Rectangles are sorted on the x-coordinate and nodes are created.
{{Expand-section|date=June 2008}}
==See also==
* [[Minimum bounding rectangle]]
* [[Spatial index]]
* [[GiST]]
==References==
<references/>
*[[Antonin Guttman]]: ''R-Trees: A Dynamic Index Structure for Spatial Searching'', Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8
*[[Lars Arge]], [[Mark de Berg]], [[Herman J.Haverkort]], [[Ke Yi]]: ''The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree'', Proc. 2004 ACM SIGMOD international conference on Management of data, pp. 347-358. ISBN 1-58113-859-8
*[[Yannis Manolopoulos]], [[Alexandros Nanopoulos]], [[Apostolos N. Papadopoulos]], [[Yannis Theodoridis]]: ''R-Trees: Theory and Applications'', Springer, 2005. ISBN 1-85233-977-2
*[http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf Norbert Beckmann, Hans- N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331]
==External links==
* [http://www.rtreeportal.org/ R-tree portal]
* [http://www-db.deis.unibo.it/courses/SI2/papers/R3.pdf R-Trees: A Dynamic Index Structure for Spatial Searching]
* [http://gis.umb.no/gis/applets/rtree2/jdk1.1/ An example java applet]
* [http://www.cliki.net/spatial-trees An R-tree implementation in Common Lisp]
[[Category:Trees (structure)]]
[[de:R-Baum]]
[[es:Árbol-R]]
[[ko:R 트리]]
[[it:R-tree]]
[[pl:R-drzewo]]
[[ru:R-дерево]]