R-Trees: A Dynamic Index Structure for Spatial Searching.
Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57@inproceedings{DBLP:conf/sigmod/Guttman84,
author = {Antonin Guttman},
editor = {Beatrice Yormark},
title = {R-Trees: A Dynamic Index Structure for Spatial Searching},
booktitle = {SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts,
June 18-21, 1984},
publisher = {ACM Press},
year = {1984},
pages = {47-57},
ee = {http://doi.acm.org/10.1145/602259.602266, db/conf/sigmod/Guttman84.html},
crossref = {DBLP:conf/sigmod/84},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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 in 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 updatmg 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.
Copyright © 1984 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Beatrice Yormark (Ed.):
SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984.
ACM Press 1984 
,
SIGMOD Record 14(2)
Contents
References
- [1]
- Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson:
System R: Relational Approach to Database Management.
ACM Trans. Database Syst. 1(2): 97-137(1976)
- [2]
- Rudolf Bayer, Edward M. McCreight:
Organization and Maintenance of Large Ordered Indexes.
SIGFIDET Workshop 1970: 107-141
- [3]
- Jon Louis Bentley:
Multidimensional Binary Search Trees Used for Associative Searching.
Commun. ACM 18(9): 509-517(1975)
- [4]
- Jon Louis Bentley, Donald F. Stanat, E. Hollings Williams Jr.:
The Complexity of Finding Fixed-Radius Near Neighbors.
Inf. Process. Lett. 6(6): 209-212(1977)
- [5]
- Jon Louis Bentley, Jerome H. Friedman:
Data Structures for Range Searching.
ACM Comput. Surv. 11(4): 397-409(1979)
- [6]
- Douglas Comer:
The Ubiquitous B-Tree.
ACM Comput. Surv. 11(2): 121-137(1979)
- [7]
- Raphael A. Finkel, Jon Louis Bentley:
Quad Trees: A Data Structure for Retrieval on Composite Keys.
Acta Inf. 4: 1-9(1974)
- [8]
- Antonin Guttman, Michael Stonebraker:
Using a Relational Database Management System for Computer Aided Design Data.
IEEE Database Eng. Bull. 5(2): 21-28(1982)
- [9]
- ...
- [10]
- ...
- [11]
- ...
- [12]
- ...
- [13]
- John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18
- [14]
- ...
- [15]
- Kai C. Wong, Murray Edelberg:
Interval Hierarchies and Their Application to Predicate Files.
ACM Trans. Database Syst. 2(3): 223-232(1977)
- [16]
- Gideon Yuval:
Finding Near Neighbors in K-Dimensional Space.
Inf. Process. Lett. 3(4): 113-114(1975)
Copyright © Sat Nov 21 00:47:38 2009
by Michael Ley (ley@uni-trier.de)
