A randomized approximate nearest neighbors algorithm

作者：Jones Peter W; Osipov Andrei^*; Rokhlin Vladimir

来源：Applied and Computational Harmonic Analysis, 2013, 34(3): 415-444.

DOI：10.1016/j.acha.2012.07.003

• Approximate nearest neighbors
• Randomized algorithms
• Fast random rotations

We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. Given N points {x(j)} in R-d, the algorithm attempts to find k nearest neighbors for each of x(j), where k is a user-specified integer parameter. The algorithm is iterative, and its CPU time requirements are proportional to T . N . (d . (log d) + k . (d + logk) . (log N)) + N . k(2) . (d + logk), with T the number of iterations performed. The memory requirements of the procedure are of the order N . (d + k).
A byproduct of the scheme is a data structure, permitting a rapid search for the k nearest neighbors among {x(j)} for an arbitrary point x is an element of R-d. The cost of each such query is proportional to T . (d . (log d) + log(N/k) . k . (d + logk)), and the memory requirements for the requisite data structure are of the order N . (d + k) + T . (d + N).
The algorithm utilizes random rotations and a basic divide-and-conquer scheme, followed by a local graph search. We analyze the scheme's behavior for normally distributed points {x(j)}, and illustrate its performance via several numerical examples.

• 出版日期2013-5