Analysis of Object Oriented Spatial Access Methods.

dc.contributor.authorFaloutsos, Christosen_US
dc.contributor.authorSellis, T.en_US
dc.contributor.authorRoussopoulos, N.en_US
dc.description.abstractThis 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. First, we show how the transformation of objects to higher dimensions (first proposed by Hinrichs and Nievergelt [HINR83]) can be effectively used as a tool for the analysis of R- and R+ -trees. Second, in this paper we provide the first known analysis of R-trees. Although formulas are given for objects in one dimension (line segments), they can be easily generalized for objects of higher dimensions as well. 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.en_US
dc.format.extent828736 bytes
dc.relation.ispartofseriesISR; TR 1987-30en_US
dc.titleAnalysis of Object Oriented Spatial Access Methods.en_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
809.31 KB
Adobe Portable Document Format