The R+ -Tree: A Dynamic Index for Multi-Dimensional Objects.

Loading...
Thumbnail Image

Files

TR_87-32.pdf (942.46 KB)
No. of downloads: 2763

Publication or External Link

Date

1987

Advisor

Citation

DRUM DOI

Abstract

The problem of indexing multidimensional objects is considered. First, a classification of existing methods in given along with a discussion of the major issues involved in multidimensional data indexing. Second, a variation to Guttman's R-trees (R+ -trees) that avoids overlapping rectangles in intermediate nodes of the tree is introduced. Algorithms for searching, updating, initial packing and reorganization of the structure are discussed in detail. Finally, we provide analytical results indicating that R+ -tree achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles.

Notes

Rights