Adaptive Multi-Stage Distance Join Processing Hyoseop Shin, Bongki Moon, and Sukho Lee   View Paper (PDF)   Return to Research Sessions Abstract A spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. Additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in on-line query processing or internet search environments. These requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. In this paper, we first present an efficient k-distance join algorithm that uses spatial indexes such as R-trees. Bidirectional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. Furthermore, we propose adaptive multi-stage algorithms for k-distance join and incremental distance join operations. Our performance study shows that the proposed adaptive multi-stage algorithms outperform previous work by up to an order of magnitude for both k-distance join and incremental distance join queries, under various operational conditions. References Note: References link to DBLP on the Web. [1] Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter : Scalable Sweeping-Based Spatial Join. VLDB 1998 : 570-581 [2] Sunil Arya , David M. Mount , Onuttom Narayan : Accounting for Boundary Effects in Nearest Neighbor Searching. Symposium on Computational Geometry 1995 : 336-344 [3] 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 [4] Stefan Berchtold , Bernhard Ertl , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl : Fast Nearest Neighbor Search in High-Dimensional Space. ICDE 1998 : 209-218 [5] Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel : The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996 : 28-39 [6] Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger : Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994 : 197-208 [7] Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger : Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993 : 237-246 [8] Michael J. Carey , Donald Kossmann : On Saying "Enough Already!" in SQL. SIGMOD Conference 1997 : 219-230 [9] Michael J. Carey , Donald Kossmann : Reducing the Braking Distance of an SQL Query Engine. VLDB 1998 : 158-169 [10] Donko Donjerkovic , Raghu Ramakrishnan : Probabilistic Optimization of Top N Queries. VLDB 1999 : 411-422 [11] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [12] Gisli R. Hjaltason , Hanan Samet : Ranking in Spatial Databases. SSD 1995 : 83-95 [13] Gisli R. Hjaltason , Hanan Samet : Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998 : 237-248 [14] Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas : Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996 : 215-226 [15] Ming-Ling Lo , Chinya V. Ravishankar : Spatial Joins Using Seeded Trees. SIGMOD Conference 1994 : 209-220 [16] Ming-Ling Lo , Chinya V. Ravishankar : Spatial Hash-Joins. SIGMOD Conf. 1996 : 247-258 [17] ... [18] Jack A. Orenstein : A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990 : 343-352 [19] Jignesh M. Patel , David J. DeWitt : Partition Based Spatial-Merge Join. SIGMOD Conf. 1996 : 259-270 [20] Franco P. Preparata , Michael Ian Shamos : Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3 [21] Nick Roussopoulos , Stephen Kelley , Frédéic Vincent : Nearest Neighbor Queries. SIGMOD Conference 1995 : 71-79 [22] Thomas Seidl , Hans-Peter Kriegel : Optimal Multi-Step k-Nearest Neighbor Search. SIGMOD Conference 1998 : 154-165 BIBTEX @inproceedings{DBLP:conf/sigmod/MoonSL00,   author    = {Hyoseop Shin and                 Bongki Moon and                 Sukho Lee},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Adaptive Multi-Stage Distance Join Processing},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {343-354},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.