Rtree
Rtree  

Type  tree  
Invented  1984  
Invented by  Antonin Guttman  
Time complexity in big O notation  

Rtrees are tree data structures used for spatial access methods, i.e., for indexing multidimensional information such as geographical coordinates, rectangles or polygons. The Rtree was proposed by Antonin Guttman in 1984^{[1]} and has found significant use in both theoretical and applied contexts.^{[2]} A common realworld usage for an Rtree 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 Rtree can also accelerate nearest neighbor search^{[3]} for various distance metrics, including greatcircle distance.^{[4]}
Contents
Rtree idea
The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in Rtree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object; at higher levels the aggregation of an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set.
Similar to the Btree, the Rtree is also a balanced search tree (so all leaf nodes are at the same height), organizes the data in pages, and is designed for storage on disk (as used in databases). Each page can contain a maximum number of entries, often denoted as . It also guarantees a minimum fill (except for the root node), however best performance has been experienced with a minimum fill of 30%–40% of the maximum number of entries (Btrees guarantee 50% page fill, and B*trees even 66%). The reason for this is the more complex balancing required for spatial data as opposed to linear data stored in Btrees.
As with most trees, the searching algorithms (e.g., intersection, containment, nearest neighbor search) are rather simple. The key idea is to use the bounding boxes to decide whether or not to search inside a subtree. In this way, most of the nodes in the tree are never read during a search. Like Btrees, this makes Rtrees suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory.
The key difficulty of Rtree is to build an efficient tree that on one hand is balanced (so the leaf nodes are at the same height) on the other hand the rectangles do not cover too much empty space and do not overlap too much (so that during search, fewer subtrees need to be processed). For example, the original idea for inserting elements to obtain an efficient tree is to always insert into the subtree that requires least enlargement of its bounding box. Once that page is full, the data is split into two sets that should cover the minimal area each. Most of the research and improvements for Rtrees aims at improving the way the tree is built and can be grouped into two objectives: building an efficient tree from scratch (known as bulkloading) and performing changes on an existing tree (insertion and deletion).
Rtrees do not guarantee good worstcase performance, but generally perform well with realworld data.^{[5]} While more of theoretical interest, the (bulkloaded) Priority Rtree variant of the Rtree is worstcase optimal,^{[6]} but due to the increased complexity, has not received much attention in practical applications so far.
When data is organized in an Rtree, the neighbors within a given distance r and the k nearest neighbors (for any L^{p}Norm) of all points can efficiently be computed using a spatial join.^{[7]}^{[8]} This is beneficial for many algorithms based on such queries, for example the Local Outlier Factor. DeLiClu,^{[9]} DensityLinkClustering is a cluster analysis algorithm that uses the Rtree structure for a similar kind of spatial join to efficiently compute an OPTICS clustering.
Variants
Algorithm
Data layout
Data in Rtrees is organized in pages, that can have a variable number of entries (up to some predefined maximum, and usually above a minimum fill). Each entry within a nonleaf node stores two pieces of data: a way of identifying a child node, and the bounding box of all entries within this child node. Leaf nodes store the data required for each child, often a point or bounding box representing the child and an external identifier for the child. For point data, the leaf entries can be just the points themselves. For polygon data (that often requires the storage of large polygons) the common setup is to store only the MBR (minimum bounding rectangle) of the polygon along with a unique identifier in the tree.
Search
In range searching, 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.
For priority search such as nearest neighbor search, the query consists of a point or rectangle. The root node is inserted into the priority queue. Until the queue is empty or the desired number of results have been returned the search continues by processing the nearest entry in the queue. Tree nodes are expanded and their children reinserted. Leaf entries are returned when encountered in the queue.^{[10]} This approach can be used with various distance metrics, including greatcircle distance for geographic data.^{[4]}
Insertion
To insert an object, the tree is traversed recursively from the root node. At each step, all rectangles in the current directory node are examined, and a candidate is chosen using a heuristic such as choosing the rectangle which requires least enlargement. The search then descends into this page, until reaching a leaf node. If the leaf node is full, it must be split before the insertion is made. Again, since an exhaustive search is too expensive, a heuristic is employed to split the node into two. Adding the newly created node to the previous level, this level can again overflow, and these overflows can propagate up to the root node; when this node also overflows, a new root node is created and the tree has increased in height.
Choosing the insertion subtree
At each level, the algorithm needs to decide in which subtree to insert the new data object. When a data object is fully contained in a single rectangle, the choice is clear. When there are multiple options or rectangles in need of enlargement, the choice can have a significant impact on the performance of the tree.
In the classic Rtree, objects are inserted into the subtree that needs the least enlargement. In the more advanced R*tree, a mixed heuristic is employed. At leaf level, it tries to minimize the overlap (in case of ties, prefer least enlargement and then least area); at the higher levels, it behaves similar to the Rtree, but on ties again preferring the subtree with smaller area. The decreased overlap of rectangles in the R*tree is one of the key benefits over the traditional Rtree (this is also a consequence of the other heuristics used, not only the subtree choosing).
Splitting an overflowing node
Since redistributing all objects of a node into two nodes has an exponential number of options, a heuristic needs to be employed to find the best split. In the classic Rtree, Guttman proposed two such heuristics, called QuadraticSplit and LinearSplit. In quadratic split, the algorithm searches for the pair of rectangles that is the worst combination to have in the same node, and puts them as initial objects into the two new groups. It then searches for the entry which has the strongest preference for one of the groups (in terms of area increase) and assigns the object to this group until all objects are assigned (satisfying the minimum fill).
There are other splitting strategies such as Greene's Split,^{[11]} the R*tree splitting heuristic^{[12]} (which again tries to minimize overlap, but also prefers quadratic pages) or the linear split algorithm proposed by Ang and Tan^{[13]} (which however can produce very irregular rectangles, which are less performant for many real world range and window queries). In addition to having a more advanced splitting heuristic, the R*tree also tries to avoid splitting a node by reinserting some of the node members, which is similar to the way a Btree balances overflowing nodes. This was shown to also reduce overlap and thus increase tree performance.
Finally, the Xtree^{[14]} can be seen as a R*tree variant that can also decide to not split a node, but construct a socalled supernode containing all the extra entries, when it doesn't find a good split (in particular for highdimensional data).
This strategy produces sliced pages, which often yield bad query performance.
The pages overlap much less since the R*tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy prefers quadratic pages, which yields better performance for common map applications.
The leaf pages do not overlap at all, and the directory pages overlap only little. This is a very efficient tree, but it requires the data to be completely known beforehand.
Splitting these pages is, however, much more complicated and pages usually overlap much more.
Deletion
Deleting an entry from a page may require updating the bounding rectangles of parent pages. However, when a page is underfull, it will not be balanced with its neighbors. Instead, the page will be dissolved and all its children (which may be subtrees, not only leaf objects) will be reinserted. If during this process the root node has a single element, the tree height can decrease.
This section needs expansion. You can help by adding to it. (October 2011)

Bulkloading
 NearestX – Objects are sorted by their first coordinate ("X") and then split into pages of the desired size.
 Packed Hilbert Rtree – variation of NearestX, but sorting using the Hilbert value of the center of a rectangle instead of using the X coordinate. There is no guarantee the pages will not overlap.
 SortTileRecursive (STR):^{[15]} Another variation of NearestX, that estimates the total number of leaves required as , the required split factor in each dimension to achieve this as , then repeatedly splits each dimensions successively into equal sized partitions using 1dimensional sorting. The resulting pages, if they occupy more than one page, are again bulkloaded using the same algorithm. For point data, the leaf nodes will not overlap, and "tile" the data space into approximately equal sized pages.
 Overlap Minimizing Topdown (OMT):^{[16]} Improvement over STR using a topdown approach which minimizes overlaps between slices and improves query performance.
 Priority Rtree
This section needs expansion. You can help by adding to it. (June 2008)

See also
 Segment tree
 Interval tree – A degenerate Rtree for one dimension (usually time).
 Bounding volume hierarchy
 Spatial index
 GiST
References
 ^ ^{a} ^{b} ^{c} Guttman, A. (1984). "RTrees: A Dynamic Index Structure for Spatial Searching". Proceedings of the 1984 ACM SIGMOD international conference on Management of data – SIGMOD '84 (PDF). p. 47. doi:10.1145/602259.602266. ISBN 0897911288.
 ^ Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). RTrees: Theory and Applications. Springer. ISBN 9781852339777. Retrieved 8 October 2011.
 ^ Roussopoulos, N.; Kelley, S.; Vincent, F. D. R. (1995). "Nearest neighbor queries". Proceedings of the 1995 ACM SIGMOD international conference on Management of data – SIGMOD '95. p. 71. doi:10.1145/223784.223794. ISBN 0897917316.
 ^ ^{a} ^{b} Schubert, E.; Zimek, A.; Kriegel, H. P. (2013). "Geodetic Distance Queries on RTrees for Indexing Geographic Data". Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science. 8098. p. 146. doi:10.1007/9783642402357_9. ISBN 9783642402340.
 ^ Hwang, S.; Kwon, K.; Cha, S. K.; Lee, B. S. (2003). "Performance Evaluation of MainMemory Rtree Variants". Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science. 2750. p. 10. doi:10.1007/9783540450726_2. ISBN 9783540405351.
 ^ Arge, L.; De Berg, M.; Haverkort, H. J.; Yi, K. (2004). "The Priority Rtree". Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD '04 (PDF). p. 347. doi:10.1145/1007568.1007608. ISBN 1581138598.
 ^ Brinkhoff, T.; Kriegel, H. P.; Seeger, B. (1993). "Efficient processing of spatial joins using Rtrees". ACM SIGMOD Record. 22 (2): 237. doi:10.1145/170036.170075.
 ^ Böhm, Christian; Krebs, Florian (20030901). "Supporting KDD Applications by the kNearest Neighbor Join". Database and Expert Systems Applications. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg: 504–516. doi:10.1007/9783540452270_50. ISBN 9783540408062.
 ^ Achtert, E.; Böhm, C.; Kröger, P. (2006). "DeLiClu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". LNCS: Advances in Knowledge Discovery and Data Mining. Lecture Notes in Computer Science. 3918: 119–128. doi:10.1007/11731139_16. ISBN 9783540332060.
 ^ Kuan, J.; Lewis, P. (1997). "Fast k nearest neighbour search for Rtree family". Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Theme: Trends in Information Systems Engineering and Wireless Multimedia Communications (Cat. No.97TH8237). p. 924. doi:10.1109/ICICS.1997.652114. ISBN 0780336763.
 ^ ^{a} ^{b} Greene, D. (1989). "An implementation and performance analysis of spatial data access methods". [1989] Proceedings. Fifth International Conference on Data Engineering. pp. 606–615. doi:10.1109/ICDE.1989.47268. ISBN 0818619155.
 ^ ^{a} ^{b} Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*tree: an efficient and robust access method for points and rectangles". Proceedings of the 1990 ACM SIGMOD international conference on Management of data – SIGMOD '90 (PDF). p. 322. doi:10.1145/93597.98741. ISBN 0897913655.
 ^ ^{a} ^{b} Ang, C. H.; Tan, T. C. (1997). "New linear node splitting algorithm for Rtrees". In Scholl, Michel; Voisard, Agnès. Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997. Lecture Notes in Computer Science. 1262. Springer. pp. 337–349. doi:10.1007/3540632387_38.
 ^ Berchtold, Stefan; Keim, Daniel A.; Kriegel, HansPeter (1996). "The XTree: An Index Structure for HighDimensional Data". Proceedings of the 22nd VLDB Conference. Mumbai, India: 28–39.
 ^ Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (February 1997). "STR: A Simple and Efficient Algorithm for RTree Packing".
 ^ Lee, Taewon; Lee, Sukho (June 2003). "OMT: Overlap Minimizing Topdown Bulk Loading Algorithm for Rtree" (PDF).