Analysis of object oriented spatial access methods

1 December 1987

journal article
Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record

Vol. 16 (3) , 426-439
https://doi.org/10.1145/38714.38758

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.

Keywords

This publication has 7 references indexed in Scilit:

Spatial query processing in an object-oriented database system
Published by Association for Computing Machinery (ACM) ,1986
Direct spatial search on pictorial databases using packed R-trees
Published by Association for Computing Machinery (ACM) ,1985
The Quadtree and Related Hierarchical Data Structures
ACM Computing Surveys, 1984
The Grid File
ACM Transactions on Database Systems, 1984
R-trees
Published by Association for Computing Machinery (ACM) ,1984
The K-D-B-tree
Published by Association for Computing Machinery (ACM) ,1981
Multidimensional binary search trees used for associative searching
Communications of the ACM, 1975