Antonin Guttman
ABSTRACT
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
- M Astrahan, et al , System R Relational Approach to Database Management, ACM Transactions on Database Systems 1, 2 (June 1976), 97-137 Google Scholar
Digital Library
- R Bayer and E McCreight, Organization and Maintenance of Large Ordered Indices, Proc 1970 ACM-SIGFIDET Workshop on Data Description and Access, Houston, Texas, Nov. 1970, 107-141Google Scholar
- J L Bentley, Multidimensional Binary Search Trees Used for Associative Searching, Communications of the ACM 18, 9 (September 1975), 509-517 Google ScholarDigital Library
- J L Bentley, D F. Stanat and E H Williams, Jr, The complexity of fixed-radius near neighbor searching, Inf Proc Lett 6, 6 (December 1977) 209-212Google ScholarCross Ref
- J L Bentley and J H Friedman, Data Structures for Range Searching, Computing Surveys 11, 4 (December 1979), 397-409 Google ScholarDigital Library
- D Comer, The Ubiquitous B-tree, Computing Surveys 11, 2 (1979), 121-138 Google ScholarDigital Library
- R A Finkel and J L Bentley, Quad Trees - A Data Structure for Retrieval on Composite Keys, Acta Informatica 4, (1974), 1-9Google ScholarDigital Library
- A Guttman and M Stonebraker, Using a Relational Database Management System for Computer Aided Design Data, IEEE Database Engineering 5, 2 (June 1982)Google Scholar
- G Held, M Stonebraker and E Wong, INGRES - A Relational Data Base System, Proc AFIPS 1975 NCC 44, (1975) 409-416Google Scholar
- K Hinrichs and J Nievergelt, The Grid File A Data Structure Designed to Support Proximity Queries on Spatial Objects, Nr 54, Institut fur Informatik, Eidgenossische Technische Hochschule, Zurich, July 1983Google Scholar
- M G. H Katevenis, R. W Sherburne, D A Patterson and C H Séquin, The RISC II Micro-Architecture, Proc VLSI 83 Conference, Trondheim, Norway, August 1983Google Scholar
- J K Ousterhout, Corner Stitching A Data Structuring Technique for VLSI Layout Tools, Computer Science Report Computer Science Dept 82/114, University of California, Berkeley, 1982 Google ScholarDigital Library
- J T Robinson, The K-D-B Tree A Search Structure for Large Multidimensional Dynamic Indexes, ACM-SIGMOD Conference Proc , April 1981, 10-18 Google ScholarDigital Library
- M Stonebraker, B Rubenstein and A Guttman, Application of Abstract Data Types and Abstract Indices to CAD Data Bases, Memorandum No UCE/ERL M83/3, Electronics Research Laboratory, University of California, Berkeley, January 1983Google Scholar
- K C Wong and M Edelberg, Interval Hierarchies and Their Application to Predicate Files, ACM Transactions on Database Systems 2, 3 (September 1977), 223-232 Google ScholarDigital Library
- G. Yuval, Finding Near Neighbors in k-dimensional Space, Inf Proc Lett 3, 4 (March 1975), 113-114Google ScholarCross Ref
- R-trees: a dynamic index structure for spatial searching
Recommendations
R-trees: a dynamic index structure for spatial searching
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, ...
Master-Client R-Trees: A New Parallel R-Tree Architecture
SSDBM '99: Proceedings of the 11th International Conference on Scientific and Statistical Database ManagementScientific databases must be able to efficiently run subset retrievals of multi-dimensional data sets. If the data sets are very large significant retrieval speedups can be obtained via parallelism. In this paper we present a new parallel distributed ...
Parallel R-trees
SIGMOD '92: Proceedings of the 1992 ACM SIGMOD international conference on Management of dataWe consider the problem of exploiting parallelism to accelerate the performance of spacial access methods and specifically, R-trees [11]. Our goal is to design a server for spatial data, so that to maximize the throughput of range queries. This can be ...
Comments