Analysis of object oriented spatial access methods
Christos Faloutsos, Timos Sellis, Nick Roussopoulos · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1987
This paper provides an analysis of R-trees and a variation (R+-trees) that avoids overlapping rectangles in intermediate nodes of the tree. The main contributions of the paper are the following. We provide the first known analysis of R-trees. Although formulas are given for objects in one dimension (line segments), they can be generalized for objects in higher dimensions as well. We show how the transformation of objects to higher dimensions [HINR83] can be effectively used as a tool for the analysis of R- and R+- trees. Finally, we derive formulas for R+-trees and compare the two methods analytically. The results we obtained show that R+-trees require less than half the disk accesses required by a corresponding R-tree when searching files of real life sizes R+-trees are clearly superior in cases where there are few long segments and a lot of small ones.
Cited by 152 works. doi:10.1145/38713.38758
Authors
References
- R-trees
- Multidimensional binary search trees used for associative searching
- The Quadtree and Related Hierarchical Data Structures
- The Grid File
- The K-D-B-tree
- Direct spatial search on pictorial databases using packed R-trees
- Spatial query processing in an object-oriented database system
- Picture Query Languages for Pictorial Data-Base Systems
- New features for a relational database system to support computer aided design