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 a...

Full description

Saved in:
Bibliographic Details
Published in:Pattern recognition 2007-02, Vol.40 (2), p.351-359
Main Authors: Lai, Jim Z.C., Liaw, Yi-Ching, Liu, Julie
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Fast search algorithm
Information theory
Information, signal and communications theory
Intrinsic dimension
Nearest neighbors
Projection value
Telecommunications and information theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0031-3203
1873-5142
DOI:10.1016/j.patcog.2006.04.024