dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331
@inproceedings{DBLP:conf/sigmod/BeckmannKSS90,
  author    = {Norbert Beckmann and
               Hans-Peter Kriegel and
               Ralf Schneider and
               Bernhard Seeger},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {The R*-Tree: An Efficient and Robust Access Method for Points
               and Rectangles},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {322-331},
  ee        = {http://doi.acm.org/10.1145/93597.98741},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The R-tree, one of the most popular access methods for rectangles, is based on the heuristic optimization of the area of the enclosing rectangle in each inner node. By running numerous experiments in a standardized testbed under highly varying data, queries and operations, we were able to design the R*-tree which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory. Using our standardized testbed in an exhaustive performance comparison, it turned out that the R*-tree clearly outperforms the existing R-tree variants Guttman's linear and quadratic R-tree and Greene's variant of the R-tree. This superiority of the R*-tree holds for different types of queries and operations, such as map overlay, for both rectangles and multidimensional points in all experiments. From a practical point of view the R*-tree is very attractive because of the following two reasons: 1 it efficiently supports point and spatial data at the same time and 2 its implementation cost is only slightly higher than that of other R-trees.

Copyright © 1990 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 ...

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

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library


References

[Gre 89]
Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut 84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hin 85]
...
[Knu 73]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KSSS 89]
Hans-Peter Kriegel, Michael Schiwietz: Performance Comparison of Point and Spatial Access Methods. SSD 1989: 89-114 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NHS 84]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RL 85]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SK 88]
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SK 90]
Bernhard Seeger, Hans-Peter Kriegel: Design, Implementation and Performance Comparison of the Buddy-Tree. DEXA 1990: 203-207 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:05 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page