Abstract

The problem of indexing multidimensional objects is considered. First, a classification of existing methods is 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+-trees achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles.

Keywords

Search engine indexingGuttman scaleComputer scienceR-treeTree (set theory)Index (typography)Multidimensional dataTheoretical computer scienceB-treeData miningSegment treeTree structureAlgorithmMathematicsInterval treeBinary treeCombinatoricsArtificial intelligenceSpatial databaseSpatial analysisStatistics

Affiliated Institutions

Related Publications

R-trees

Antonin Guttman

In order to handle spatial data efficiently, as required in computer aided design and geo-data applications, a database system needs an index mechanism that will help it retriev...

1984 6534 citations

The K-D-B-tree

John T. Robinson

The problem of retrieving multikey records via range queries from a large, dynamic index is considered. By large it is meant that most of the index must be stored on secondary m...

1981 885 citations

Additive Similarity Trees

Shmuel Sattath , Amos Tversky

Similarity data can be represented by additive trees. In this model, objects are represented by the external nodes of a tree, and the dissimilarity between objects is the length...

1977 Psychometrika 598 citations

Best-first Decision Tree Learning

Haijian Shi

Decision trees are potentially powerful predictors and explicitly represent the structure of a dataset. Standard decision tree learners such as C4.5 expand nodes in depth-first ...

2007 Research Commons (University of Waikato) 229 citations

Publication Info

Year
2018
Type
article
Pages
507-518
Citations
1263
Access
Closed

External Links

View on DOI.org

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

1263
OpenAlex

Cite This

Timos Sellis, Nick Roussopoulos, Christos Faloutsos (2018). The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. Very Large Data Bases , 507-518. https://doi.org/10.1184/r1/6610748.v1

Identifiers

DOI
10.1184/r1/6610748.v1