ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Scalable Sweeping-Based Spatial Join.

Lars Arge, Octavian Procopiuc, Sridhar Ramaswamy, Torsten Suel, Jeffrey Scott Vitter: Scalable Sweeping-Based Spatial Join. VLDB 1998: 570-581
@inproceedings{DBLP:conf/vldb/ArgePRSV98,
  author    = {Lars Arge and
               Octavian Procopiuc and
               Sridhar Ramaswamy and
               Torsten Suel and
               Jeffrey Scott Vitter},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {Scalable Sweeping-Based Spatial Join},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {570-581},
  ee        = {db/conf/vldb/ArgePRSV98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper, we consider the filter step of the spatial join problem, for the case where neither of the inputs are indexed. We present a new algorithm, Scalable Sweeping-Based Spatial Join (SSSJ), that achieves both efficiency on real-life data and robustness against highly skewed and worst-case data sets. The algorithm combines a method with theoretically optimal bounds on I/O transfers based on the recently proposed distribution-sweeping technique with a highly optimized implementation of internal-memory plane-sweeping. We present experimental results based on an efficient implementation of the SSSJ algorithm, and compare it to the state-of- the-art Partition-Based Spatial-Merge (PBSM) algorithm of Patel and Dewitt.

Copyright © 1998 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 DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

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

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[Aga96]
Ramesh C. Agarwal: A Super Scalar Sort Algorithm for RISC Processors. SIGMOD Conference 1996: 240-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AM]
...
[APR+98]
...
[ARC93]
...
[Arg95]
Lars Arge: The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract). WADS 1995: 334-345 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Arg97]
...
[AV88]
Alok Aggarwal, Jeffrey Scott Vitter: The Input/Output Complexity of Sorting and Related Problems. Commun. ACM 31(9): 1116-1127(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AVV98]
...
[Ben77]
...
[BG92]
Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992) 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
[Chi95]
Yi-Jen Chiang: Experiments on the Practical I/O Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep. WADS 1995: 346-357 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CLR90]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company 1989, ISBN 0-262-03141-8,0-07-013143-0
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DDC+97]
Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson: High-Performance Sorting on Networks of Workstations. SIGMOD Conference 1997: 243-254 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ede83]
...
[GS87]
...
[GTVV93]
Michael T. Goodrich, Jyh-Jong Tsay, Darren Erik Vengroff, Jeffrey Scott Vitter: External-Memory Computational Geometry (Preliminary Version). FOCS 1993: 714-723 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GŁn93]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut85]
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
[Han91]
Eric N. Hanson: The Interval Skip List: A Data Structure for Finding All Intervals that Overlap a Point. WADS 1991: 153-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HJR97]
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hs92]
Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Int97]
...
[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
[KS97]
Nick Koudas, Kenneth C. Sevcik: Size Separation Spatial Join. SIGMOD Conference 1997: 324-335 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
[McC85]
Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NBC+94]
Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet: AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994: 233-242 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
[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
[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
[PS85]
Franco P. Preparata, Michael Ian Shamos: Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Pug90]
William Pugh: Skip Lists: A Probabilistic Alternative to Balanced Trees. Commun. ACM 33(6): 668-676(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rot91]
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sam89]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
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
[Tig92]
...
[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
[Ven94]
...
[Ven95]
...
[VV96]
...

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