Fast k-nearest-neighbor search based on projection and triangular inequality
Fast k-nearest-neighbor search based on projection and triangular inequality
复制标题
DOI：
10.1016/j.patcog.2006.04.024
复制
发表时间：
2007-02-01
影响因子：
8
通讯作者：
Liu, Julie
中科院分区：
文献类型：
--
作者：
Lai, Jim Z. C.;Liaw, Yi-Ching;Liu, Julie
本文提出了一种新的算法，寻找k点是最接近的查询点。一些不等式被用来删除不可能的数据点，减少距离计算。我们的算法利用一个数据点的功能，拒绝不太可能的候选人的查询点，可以消除许多不太可能的数据点，这不能被其他可用的算法拒绝。实验结果表明，在大多数情况下，该算法在计算时间和距离计算次数上都上级其他方法，并且在维数较高的大数据集上效果更显著。与现有的方法相比，我们的方法可以减少计算时间和距离计算的数量显着。(c)2006模式识别学会。由爱思唯尔有限公司出版。保留所有权利。
In this paper, a novel algorithm for finding k points that are closest to a query point is presented. Some inequalities are used to delete impossible data points and reduce distance computations. Our algorithm makes use of a data point's feature to reject unlikely candidates for a query point and can eliminate many of the unlikely data points, which cannot be rejected by other available algorithms. Experimental results show that our algorithm is superior to other methods in terms of computing time and the number of distance calculations in most cases and is more remarkable, if a larger data set with higher dimension is used. Compared with available approaches, our method can reduce the computing time and number of distance calculations significantly. (c) 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.