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

Size Separation Spatial Join.

Nick Koudas, Kenneth C. Sevcik: Size Separation Spatial Join. SIGMOD Conference 1997: 324-335
@inproceedings{DBLP:conf/sigmod/KoudasS97,
  author    = {Nick Koudas and
               Kenneth C. Sevcik},
  editor    = {Joan Peckham},
  title     = {Size Separation Spatial Join},
  booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
               on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
  publisher = {ACM Press},
  year      = {1997},
  pages     = {324-335},
  ee        = {http://doi.acm.org/10.1145/253260.253340},
  crossref  = {DBLP:conf/sigmod/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We introduce a new algorithm to compute the spatial join of two or more spatial data sets, when indexes are not available on them. Size Separation Spatial Join (S³J) imposes a hierarchical decomposition of the data space and, in contrast with previous approaches, requires no replication of entities from the input data sets. Thus its execution time depends only on the sizes of the joined data sets.

We describe S³J and present an analytical evaluation of its l/O and processor requirements comparing them with those of previously proposed algorithms for the same problem. We show that S³J has relatively simple cost estimation formulas that can be exploited by a query optimizer. S³J can be efficiently implemented using software already present in many relational systems. In addition, we introduce Dynamic Spatial Bitmaps (DSB), a new technique that enables S³J to dynamically or statically exploit bitmap query processing techniques.

Finally, we present experimental results for a prototype implementation of S³J involving real and synthetic data sets for a variety of data distributions. Our experimental results are consistent with our analytical observations and demonstrate the performance benefits of S³J over alternative approaches that have been proposed recently.

Copyright © 1997 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 1, SIGMOD '93-'97" and ...

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

Printed Edition

Joan Peckham (Ed.): SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA. ACM Press 1997 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 26(2), June 1997
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1456 KB]

References

[Bia69]
T. Bially: Space-Filling Curves: Their Generation and Their Application to Bandwidth Reduction. IEEE Transactions on Information Theory 15(6): 658-664(1969) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKS93]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKSS94]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bur91]
...
[Gut84]
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
[KS96]
...
[LR95]
Ming-Ling Lo, Chinya V. Ravishankar: Generating Seeded Trees from Data Sets. SSD 1995: 328-347 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LR96]
Ming-Ling Lo, Chinya V. Ravishankar: Spatial Hash-Joins. SIGMOD Conference 1996: 247-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OG95]
Patrick E. O'Neil, Goetz Graefe: Multi-Table Joins Through Bitmapped Join Indices. SIGMOD Record 24(3): 8-11(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[O'N96]
...
[Ore86]
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
[PD96]
Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rot93]
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SK96]
Kenneth C. Sevcik, Nick Koudas: Filter Trees for Managing Spatial Data over a Range of Size Granularities. VLDB 1996: 16-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SM96]
Michael Stonebraker, Dorothy Moore: Object-Relational DBMSs: The Next Great Wave. Morgan Kaufmann 1996, ISBN 1-55860-397-2
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRF87]
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
[Val87]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:15 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