Fast k-nearest-neighbor search based on projection and triangular inequality

摘要

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.