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}
}

BibTeX

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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Beatrice Yormark (Ed.): SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984. ACM Press 1984 BibTeX , SIGMOD Record 14(2)
Contents

Online Edition: ACM Digital Library

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) BibTeX
[2]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indexes. SIGFIDET Workshop 1970: 107-141 BibTeX
[3]: Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[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) BibTeX
[5]: Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX
[6]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[7]: Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX
[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) BibTeX
[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 BibTeX
[14]: ...
[15]: Kai C. Wong, Murray Edelberg: Interval Hierarchies and Their Application to Predicate Files. ACM Trans. Database Syst. 2(3): 223-232(1977) BibTeX
[16]: Gideon Yuval: Finding Near Neighbors in K-Dimensional Space. Inf. Process. Lett. 3(4): 113-114(1975) BibTeX

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]