ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Techniques for Design and Implementation of Efficient Spatial Access Methods.

Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371
@inproceedings{DBLP:conf/vldb/SeegerK88,
  author    = {Bernhard Seeger and
               Hans-Peter Kriegel},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Techniques for Design and Implementation of Efficient Spatial
               Access Methods},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {360-371},
  ee        = {db/conf/vldb/SeegerK88.html},
  crossref  = {DBLP:conf/vldb/88},
  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 management system (DBMS) needs an access method that will help it retrieve data items quickly according to their spatial location. In this paper we present a classification of existing spatial access methods and show that they use one of the following three techniques: clipping, overlapping regions, and transformation. From a practical point of view we provide a tool box supporting simple design of a spatial access method for a given point access method using one of the above techniques. We analyze the technique of transformation in more detail and show that our new concept of asymmetric partitioning is more retrieval efficient than the traditional symmetric approach. Furthermore we suggest a hybrid method combining the techniques of overlapping regions and transformation and provide an analysis and comparison of our new method. For data for which an analysis of R- and R+-trees was available, these comparisons demonstrate a superiority of our scheme.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Ben 75]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bur 83]
Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Com 79]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HKSS 88]
...
[FNPS 79]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FSR 87]
Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 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
[KS 86]
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS 87]
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Dynamic Quantile Hashing is Very Efficient for Non-Uniform Record Distributions. ICDE 1987: 10-17 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS 88]
Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lar 80]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lit 80]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MOD 87]
...
[MT 83]
...
[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
[NH 85]
Jürg Nievergelt, Klaus Hinrichs: Storage and Access Structures for Geometric Data Bases. FODO 1985: 441-455 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ooi 87]
...
[Ore 86]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OM 84]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Oto 84]
Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Oto 86]
Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ouk 85]
Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rob 81]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 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
[Sam 85]
Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRF 87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SW 88]
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRG 83]
...
[TS 82]
...
[WK 85]
...

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)