- R* tree
R* tree is a variant of
R tree for indexing spatial information. R* tree supports point and spatial data at the same time with a slightly higher cost than other R-trees.It was proposed by Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger in1990 .Difference between R* trees and R trees
Minimization of both coverage and overlap is crucial to the performance of R-trees. The R*-tree attempts to reduce both, using a combination of a revised node split algorithm and the concept of forced reinsertionat node overflow. This is based on the observation that R-tree structures are highly susceptible to the order in which their entries are inserted, so an insertion-built (rather than bulk-loaded) structure is likely to be sub-optimal. Deletion and reinsertion of entries allows them to "find" a place in the tree that may be more appropriate than their original location.
When a node overflows, a portion of its entries are removed from the node and reinserted into the tree.(In order to avoid an indefinite cascade of reinsertions caused by subsequent node overflow, the reinsertion routine may be called only once in each level of the tree when inserting any one new entry.) This has the effect of producing more well-clustered groups of entries in nodes, reducing node coverage. Furthermore, actual node splits are often postponed, causing average node occupancy to rise.
Performance
*Likely significant improvement over other R tree variants, but there is overhead due to the reinsertion method.
*Efficiently supports point and spatial data at the same timeAlgorithm
The R* tree uses the same algorithm as the
R-tree for query and delete operations. The primary difference is the insert algorithm, specifically how it chooses which branch to insert the new node into and the methodology for splitting a node that is full.ee also
*
R tree
*Hilbert R-tree
*R+ tree References
* [http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331]
External links
* [http://donar.umiacs.umd.edu/quadtree/points/rtrees.html R-tree Demo]
* [http://www.cs.duke.edu/TPIE/ The TPIE Library contains a C++ R* tree implementation]
* [http://www.virtualroadside.com/blog/index.php/2008/10/04/r-tree-implementation-for-cpp/ A header-only C++ R* Tree Implementation]
* [http://research.att.com/~marioh/spatialindex/ Java and C++ implementation are in the Spatial Index Library]
Wikimedia Foundation. 2010.
