R-tree

R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods 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 convert|2|mi|km of my current location".

The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (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, 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 databases, 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. [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] ]

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.

Bulk-loading

* Sort-Tile-Recursive (STR) [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] ]
* Packed 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.

ee also

* Minimum bounding rectangle
* Spatial index
* GiST

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]