ACM SIGMOD Anthology VLDB dblp.uni-trier.de

The Impact of Global Clustering on Spatial Database Systems.

Thomas Brinkhoff, Hans-Peter Kriegel: The Impact of Global Clustering on Spatial Database Systems. VLDB 1994: 168-179
@inproceedings{DBLP:conf/vldb/BrinkhoffK94,
  author    = {Thomas Brinkhoff and
               Hans-Peter Kriegel},
  editor    = {Jorge B. Bocca and
               Matthias Jarke and
               Carlo Zaniolo},
  title     = {The Impact of Global Clustering on Spatial Database Systems},
  booktitle = {VLDB'94, Proceedings of 20th International Conference on Very
               Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile},
  publisher = {Morgan Kaufmann},
  year      = {1994},
  isbn      = {1-55860-153-8},
  pages     = {168-179},
  ee        = {db/conf/vldb/vldb94-168.html},
  crossref  = {DBLP:conf/vldb/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Global clustering has rarely been investigated in the area of spatial database systems although dramatic performance improvements can be achieved by using suitable techniques. In this paper, we propose a simple approach to global clustering called cluster organization. We will demonstrate that this cluster organization leads to considerable performance improvements without any algorithmic overhead. Based on real geographic data, we perform a detailed empirical performance evaluation and compare the cluster organization to other organization models not using global clustering. We will show that global clustering speeds up the processing of window queries as well as spatial joins without decreasing the performance of the insertion of new objects and of selective queries such as point queries. The spatial join is sped up by a factor of about 4, whereas non-selective window queries are accelerated by even higher speed up factors.

Copyright © 1994 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 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.): VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile. Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX

References

[BHKS93]
Thomas Brinkhoff, Holger Horn, Hans-Peter Kriegel, Ralf Schneider: A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems. SSD 1993: 357-376 BibTeX
[BK94]
...
[BKS93a]
...
[BKS93b]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 BibTeX
[BKSS90]
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 BibTeX
[BKSS94]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 BibTeX
[Bur86]
...
[Bur89]
...
[DS93]
Gisbert Dröge, Hans-Jörg Schek: Query-Adaptive Data Space Partitioning using Variable-Size Storage Clusters. SSD 1993: 337-356 BibTeX
[Fra91]
Andrew U. Frank: Properties of Geographic Data: Requirements for Spatial Access Methods. SSD 1991: 225-234 BibTeX
[Fre87]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
[GR93]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[HS92]
Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214 BibTeX
[HS94]
...
[HSW88]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579 BibTeX
[HSW89]
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX
[HWZ91]
...
[NHS84]
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) BibTeX
[Ore89]
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 BibTeX
[Sam90]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX
[SFGM93]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 BibTeX
[SK90]
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX
[SK91]
...
[SLM93]
Bernhard Seeger, Per-Åke Larson, Ron McFadyen: Reading a Set of Disk Pages. VLDB 1993: 592-603 BibTeX
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[Wei89]
Gerhard Weikum: Set-Oriented Disk Access to Large Complex Objects. ICDE 1989: 426-433 BibTeX

Referenced by

  1. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  2. Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Parallel Processing of Spatial Joins Using R-trees. ICDE 1996: 258-265
  3. Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:00 2009