R-trees
Antonin Guttman · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1984
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 retrieve data items quickly according to their spatial locations However, traditional indexing methods are not well suited to data objects of non-zero size located m multi-dimensional spaces In this paper we describe a dynamic index structure called an R-tree which meets this need, and give algorithms for searching and updating it. We present the results of a series of tests which indicate that the structure performs well, and conclude that it is useful for current database systems in spatial applications
Cited by 6,580 works. doi:10.1145/602259.602266
Authors
References
- Multidimensional binary search trees used for associative searching
- System R
- Quad trees a data structure for retrieval on composite keys
- Ubiquitous B-Tree
- Data Structures for Range Searching
- INGRES
- The K-D-B-tree
- The complexity of finding fixed-radius near neighbors
- Finding near neighbours in K-dimensional space
- Organization and maintenance of large ordered indices