R* tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search








  • Reinsertion method optimizes the existing tree, but increases complexity.
  • Efficiently supports point and spatial data at the same time.
Effect of different splitting heuristics on a database with Germany postal districts
R-Tree with Guttman quadratic split.[2]
There are many pages that extend from east to west all over Germany, and pages overlap a lot. This is not beneficial for most applications, that often only need a small rectangular area that intersects with many slices. 
R-Tree with Ang-Tan linear split.[3]
While the slices do not extend as far as with Guttman, the slicing problem affects almost every leaf page. Leaf pages overlap little, but directory pages do. 
R* tree topological split.[1]
The pages overlap very little since the R*-tree tries to minimize page overlap, and the reinsertions further optimized the tree. The split strategy also does not prefer slices, the resulting pages are much more useful for common map applications. 

Algorithm and complexity[edit]


Obviously, worst case query and delete complexity are thus identical to the R-Tree. The insertion strategy to the R*-tree is with \mathcal{O}(M \log M) more complex than the linear split strategy (\mathcal{O}(M)) of the R-tree, but less complex than the quadratic split strategy (\mathcal{O}(M^2)) for a page size of M objects and has little impact on the total complexity. The total insert complexity is still comparable to the R-tree: reinsertions affect at most one branch of the tree and thus \mathcal{O}(\log n) reinsertions, comparable to performing a split on a regular R-tree. So on overall, the complexity of the R*-tree is the same as that of a regular R-tree.



  2. ^ Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial Searching". Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. p. 47. doi:10.1145/602259.602266. ISBN 0897911288.  edit
  3. ^ Ang, C. H.; Tan, T. C. (1997). "New linear node splitting algorithm for R-trees". 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/3-540-63238-7_38.  edit

External links[edit]

Libraries containing R*-trees:

Demonstration and example code: