Finding the k-closest pairs in metric spaces
Finding the k-closest pairs in metric spaces
复制标题
DOI：
10.1145/1966865.1966870
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
H. Kurasawa;A. Takasu;J. Adachi
中科院分区：
文献类型：
--
作者：
H. Kurasawa;A. Takasu;J. Adachi
我们研究了在度量空间中降低搜索k个最近对的代价问题。通常，k-最近对搜索方法将k个最近对之间的上界距离初始化为无穷大，并且每当它找到距离小于该距离的对象对时，重复更新上界距离。此外，它还根据枢轴到对象的距离和三角形不等式性，对距离估计大于上限距离的不相似对进行剪枝。对于更短的上界距离和更稀疏的枢轴和对象之间的距离分布，k最近对查询的成本较小。我们提出了一种新的度量空间中基于分治的k最近对搜索方法，称为自适应多划分(AMP)。AMP从稀疏的距离分布空间中反复分割和征服对象，并在划分密集空间之前加快上界距离的收敛速度。因此，与普通的基于分而治之的方法相比，AMP算法可以剪枝许多相异对。我们将该方法与其他划分方法进行了比较，结果表明，AMP方法减少了距离计算。
We investigated the problem of reducing the cost of searching for the k closest pairs in metric spaces. In general, a k-closest pair search method initializes the upper bound distance between the k closest pairs as infinity and repeatedly updates the upper bound distance whenever it finds pairs of objects whose distances are shorter than that distance. Furthermore, it prunes dissimilar pairs whose distances are estimated as longer than the upper bound distance based on the distances from the pivot to objects and the triangle inequality. The cost of a k-closest pair query is smaller for a shorter upper bound distance and a sparser distribution of distances between the pivot and objects. We propose a new divide-and-conquer-based k-closest pair search method in metric spaces, called Adaptive Multi-Partitioning (AMP). AMP repeatedly divides and conquers objects from the sparser distance-distribution space and speeds up the convergence of the upper bound distance before partitioning the denser space. As a result, AMP can prune many dissimilar pairs compared with ordinary divide-and-conquer-based method. We compare our method with other partitioning method and show that AMP reduces distances computations.