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