ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Partition Based Spatial-Merge Join.

Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270
@inproceedings{DBLP:conf/sigmod/PatelD96,
  author    = {Jignesh M. Patel and
               David J. DeWitt},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Partition Based Spatial-Merge Join},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {259-270},
  ee        = {http://doi.acm.org/10.1145/233269.233338, db/conf/sigmod/PatelD96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper describes PBSM (Partition Based Spatial-Merge), a new algorithm for performing spatial join operation. This algorithm is especially effective when neither of the inputs to the join have an index on the joining attribute. Such a situation could arise if both inputs to the join are intermediate results in a complex query, or in a parallel environment where the inputs must be dynamically redistributed. The PBSM algorithm partitions the inputs into manageable chunks, and joins them using a computational geometry based plane-sweeping technique. This paper also presents a performance study comparing the traditional indexed nested loops join algorithm, a spatial join algorithm based on joining spatial indices, and the PBSM algorithm. These comparisons are based on complete implementations of these algorithms in Paradise, a database system for handling GIS applications. Using real data sets, the performance study examines the behavior of these spatial join algorithms in a variety of situations, including the cases when both, one, or none of the inputs to the join have an suitable index. The study also examines the effect of clustering the join inputs on the performance of these join algorithms. The performance comparisons demonstrates the feasibility, and applicability of the PBSM algorithm.

Copyright © 1996 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

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

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

References

[Arc95]
...
[Ben75]
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
[Ben79]
Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BHF93]
Ludger Becker, Klaus Hinrichs, Ulrich Finke: A New Algorithm for Computing Joins with Grid Files. ICDE 1993: 190-197 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
[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 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
[Bur86]
...
[CDF+94]
Michael J. Carey, David J. DeWitt, Michael J. Franklin, Nancy E. Hall, Mark L. McAuliffe, Jeffrey F. Naughton, Daniel T. Schuh, Marvin H. Solomon, C. K. Tan, Odysseas G. Tsatalos, Seth J. White, Michael J. Zwilling: Shoring Up Persistent Applications. SIGMOD Conference 1994: 383-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CFR87]
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
[Cor95]
...
[DKL+94]
David J. DeWitt, Navin Kabra, Jun Luo, Jignesh M. Patel, Jie-Bing Yu: Client-Server Paradise. VLDB 1994: 558-569 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DLPY93]
...
[DNSS92]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider, S. Seshadri: Practical Skew Handling in Parallel Joins. VLDB 1992: 27-40 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS87]
...
[GŁn93]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
[HNKT90]
Lilian Harada, Miyuki Nakano, Masaru Kitsuregawa, Mikio Takagi: Query Processing for Multi-Attribute Clustered Records. VLDB 1990: 59-70 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS95]
Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KHT89]
Masaru Kitsuregawa, Lilian Harada, Mikio Takagi: Join Strategies on KB-Tree Indexed Relations. ICDE 1989: 85-93 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LR94]
Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
[MC80]
...
[MGR91]
...
[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
[NS86]
...
[OM84]
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
[OM88]
Jack A. Orenstein, Frank Manola: PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans. Software Eng. 14(5): 611-629(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
[Ore89]
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ore90]
Jack A. Orenstein: A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990: 343-352 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PD]
...
[PS88]
...
[Rot91]
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SFGM93]
Michael Stonebraker, James Frew, Kenn Gardels, Jeff Meredith: The Sequoia 2000 Benchmark. SIGMOD Conference 1993: 2-11 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sto86]
Michael Stonebraker: The Case for Shared Nothing. IEEE Database Eng. Bull. 9(1): 4-9(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tig]
...
[TY95]
Kian-Lee Tan, Jeffrey Xu Yu: A Performance Study of Declustering Strategies for Parallel Spatial Databases. DEXA 1995: 157-166 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ube94]
Michael Ubell: The Montage Extensible DataBlade Achitecture. SIGMOD Conference 1994: 482 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
[ZG90]
Hansjörg Zeller, Jim Gray: An Adaptive Hash Join Algorithm for Multiuser Environments. VLDB 1990: 186-197 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:54:34 2010 by Michael Ley (ley@uni-trier.de)