Analysis of object oriented spatial access methods

Abstract

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.