R^*-tree

(data structure)

Definition: A spatial access method which splits space in hierarchically nested, possibly overlapping, boxes. The tree is height-balanced. It is similar to the R-tree, but reinserts entries upon overflow, rather than splitting.

Note: After [GG98].

Author: PEB

Implementation

In Marios Hadjieleftheriou's Spatial Index Library (C++)

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 9 October 2007.
HTML page formatted Tue Oct 9 11:54:19 2007.

Cite this as:
Paul E. Black, "R^*-tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 9 October 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/rstartree.html

R*-tree

Implementation

R^*-tree