 |
|
|
Scalable Sweeping-Based Spatial Join |
Full Paper (PDF)
|
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.
|
References, where available, link to the DBLP on the World Wide Web.
[Aga96]Ramesh C. Agarwal:
A Super Scalar Sort Algorithm for RISC Processors.
SIGMOD Conf. 1996: 240-246[AM]...
[APR+98]...
[ARC93]...
[Arg95]Lars Arge:
The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract).
WADS 1995: 334-345[Arg97]...
[AV88]Alok Aggarwal, Jeffrey Scott Vitter:
The Input/Output Complexity of Sorting and Related Problems.
CACM 31(9): 1116-1127(1988)[AVV98]...
[Ben77]...
[BG92]Ludger Becker, Ralf Hartmut Güting:
Rule-Based Optimization and Query Processing in an Extensible Geometric Database System.
TODS 17(2): 247-303(1992)[BHF93]Ludger Becker, Klaus Hinrichs, Ulrich Finke:
A New Algorithm for Computing Joins with Grid Files.
ICDE 1993: 190-197[BKS93]Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger:
Efficient Processing of Spatial Joins Using R-Trees.
SIGMOD Conference 1993: 237-246[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[Chi95]Yi-Jen Chiang:
Experiments on the Practical I/O Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep.
WADS 1995: 346-357[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 and 0-07-013143-0
[DDC+97]Andrea C. Arpaci-Dusseau, Remzi Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein, David A. Patterson:
High-Performance Sorting on Networks of Workstations.
SIGMOD Conference 1997: 243-254[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[Gün93]Oliver Günther:
Efficient Computation of Spatial Joins.
ICDE 1993: 50-59[Gut85]Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57[Han91]Eric N. Hanson:
The Interval Skip List: A Data Structure for Finding All Intervals that Overlap a Point.
WADS 1991: 153-164[HJR97]Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations.
VLDB 1997: 396-405[Hs92]Erik G. Hoel, Hanan Samet:
A Qualitative Comparison Study of Data Structures for Large Line Segment Databases.
SIGMOD Conference 1992: 205-214[Int97]...
[KHT89]Masaru Kitsuregawa, Lilian Harada, Mikio Takagi:
Join Strategies on KB-Tree Indexed Relations.
ICDE 1989: 85-93[KS97]Nick Koudas, Kenneth C. Sevcik:
Size Separation Spatial Join.
SIGMOD Conference 1997: 324-335[LR94]Ming-Ling Lo, Chinya V. Ravishankar:
Spatial Joins Using Seeded Trees.
SIGMOD Conference 1994: 209-220[LR95]Ming-Ling Lo, Chinya V. Ravishankar:
Generating Seeded Trees from Data Sets.
SSD 1995: 328-347[LR96]Ming-Ling Lo, Chinya V. Ravishankar:
Spatial Hash-Joins.
SIGMOD Conf. 1996: 247-258[McC85]Edward M. McCreight:
Priority Search Trees.
SIAM J. Comput. 14(2): 257-276(1985)[NBC+94]Chris Nyberg, Tom Barclay, Zarka Cvetanovic, Jim Gray, David B. Lomet:
AlphaSort: A RISC Machine Sort.
SIGMOD Conference 1994: 233-242[NHS84]Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik:
The Grid File: An Adaptable, Symmetric Multikey File Structure.
TODS 9(1): 38-71(1984)[OM88]Jack A. Orenstein, Frank Manola:
PROBE Spatial Data Modeling and Query Processing in an Image Database Application.
TSE 14(5): 611-629(1988)[Ore86]Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336[Ore89]Jack A. Orenstein:
Redundancy in Spatial Databases.
SIGMOD Conference 1989: 294-305[Ore90]Jack A. Orenstein:
A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces.
SIGMOD Conference 1990: 343-352[PD96]Jignesh M. Patel, David J. DeWitt:
Partition Based Spatial-Merge Join.
SIGMOD Conf. 1996: 259-270[PS85]Franco P. Preparata, Michael Ian Shamos:
Computational Geometry - An Introduction.
Springer 1985, ISBN 3-540-96131-3
[Pug90]William Pugh:
Skip Lists: A Probabilistic Alternative to Balanced Trees.
CACM 33(6): 668-676(1990)[Rot91]Doron Rotem:
Spatial Join Indices.
ICDE 1991: 500-509[Sam89]Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
[SRF87]Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518[Tig92]...
[Ube94]Michael Ubell:
The Montage Extensible DataBlade Achitecture.
SIGMOD Conference 1994: 482[Val87]Patrick Valduriez:
Join Indices.
TODS 12(2): 218-246(1987)[Ven94]...
[Ven95]...
[VV96]...
|
@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},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
