Closest pair queries in spatial databases
Closest pair queries in spatial databases
复制标题
DOI：
10.1145/342009.335414
复制
发表时间：
2000-05
期刊：
影响因子：
--
通讯作者：
Antonio Corral;Y. Manolopoulos;Y. Theodoridis;M. Vassilakopoulos
中科院分区：
文献类型：
--
作者：
Antonio Corral;Y. Manolopoulos;Y. Theodoridis;M. Vassilakopoulos
本文解决了寻找两个空间数据集之间 K 个最接近的对的问题，其中每个数据集都存储在属于 R 树家族的结构中。提出了五种不同的算法（四种递归算法和一种迭代算法）来解决这个问题。 1 个最接近的对的情况被视为特殊情况。提出了一项基于合成数据集和真实点数据集进行的实验的广泛研究。探讨了影响算法性能的基本参数的各种值，特别是两个数据集之间重叠的影响。此外，还提出了与解决相同问题的现有增量算法的算法和实验比较。在大多数情况下，提出的新算法明显优于现有算法。
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.