Closest Pair Queries in Spatial Databases Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, and Michael Vassilakopoulos   View Paper (PDF)   Return to Research Sessions Abstract This paper addresses the problem of finding the K closest pairs between two spatial data sets, where each set is stored in a structure belonging in the R-tree family. Five different algorithms (four recursive and one iterative) are presented for solving this problem. The case of 1 closest pair is treated as a special case. An extensive study, based on experiments performed with synthetic as well as with real point data sets, is presented. A wide range of values for the basic parameters affecting the performance of the algorithms, especially the effect of overlap between the two data sets, is explored. Moreover, an algorithmic as well as an experimental comparison with existing incremental algorithms addressing the same problem is presented. In most settings, the new algorithms proposed clearly outperform the existing ones. References Note: References link to DBLP on the Web. [1] 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 [2] Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft : When Is ''Nearest Neighbor'' Meaningful? ICDT 1999 : 217-235 [3] Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger : Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993 : 237-246 [4] Antonio Corral , Michael Vassilakopoulos , Yannis Manolopoulos : Algorithms for Joining R-Trees and Linear Region Quadtrees. SSD 1999 : 251-269 [5] ... [6] David J. DeWitt , Navin Kabra , Jun Luo , Jignesh M. Patel , Jie-Bing Yu : Client-Server Paradise. VLDB 1994 : 558-569 [7] Martin Dietzfelbinger , Torben Hagerup , Jyrki Katajainen , Martti Penttonen : A Reliable Randomized Algorithm for the Closest-Pair Problem. J. Algorithms 25(1) : 19-51(1997) [8] Volker Gaede , Oliver Günther : Multidimensional Access Methods. Computing Surveys 30(2) : 170-231(1998) [9] Michael T. Goodrich , Jyh-Jong Tsay , Darren Erik Vengroff , Jeffrey Scott Vitter : External-Memory Computational Geometry (Preliminary Version). FOCS 1993 : 714-723 [10] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [11] Gisli R. Hjaltason , Hanan Samet : Incremental Distance Join Algorithms for Spatial Databases. SIGMOD Conference 1998 : 237-248 [12] Samir Khuller , Yossi Matias : A Simple Randomized Sieve Algorithm for the Closest-Pair Problem. Information and Computation 118(1) : 34-37(1995) [13] Scott T. Leutenegger , Mario A. Lopez : The Effect of Buffering on the Performance of R-Trees. ICDE 1998 : 164-171 [14] Nikos Mamoulis , Dimitris Papadias : Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999 : 1-12 [15] ... [16] Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis : Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999 : 44-55 [17] Apostolos Papadopoulos , Yannis Manolopoulos : Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997 : 394-408 [18] Apostolos Papadopoulos , Yannis Manolopoulos : Nearest Neighbor Queries in Shared-Nothing Environments. GeoInformatica 1(4) : 369-392(1997) [19] Jignesh M. Patel , Jie-Bing Yu , Navin Kabra , Kristin Tufte , Biswadeep Nag , Josef Burger , Nancy E. Hall , Karthikeyan Ramasamy , Roger Lueder , Curt Ellman , Jim Kupsch , Shelly Guo , David J. DeWitt , Jeffrey F. Naughton : Building a Scaleable Geo-Spatial DBMS: Technology, Implementation, and Evaluation. SIGMOD Conference 1997 : 336-347 [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] Michael Stonebraker , James Frew , Kenn Gardels , Jeff Meredith : The Sequoia 2000 Benchmark. SIGMOD Conference 1993 : 2-11 [23] Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis : Cost Models for Join Queries in Spatial Databases. ICDE 1998 : 476-483 BIBTEX @inproceedings{DBLP:conf/sigmod/CorralMTV00,   author    = {Antonio Corral and                 Yannis Manolopoulos and                 Yannis Theodoridis and                 Michael Vassilakopoulos},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Closest Pair Queries in Spatial Databases},    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     = {189-200},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.