A Randomized Approximate Nearest Neighbors Algorithm

Seminar: 
Graduate Student Seminar
Event time: 
Friday, October 15, 2010 - 9:00am to 10:00am
Location: 
215LOM
Speaker: 
Andrei Osipov
Speaker affiliation: 
Yale University
Event description: 

We present a randomized algorithm for the approximate nearest neighbor problem in ddimensional Euclidean space. Given N points {xj} in Rd, the algorithm attempts to find
k nearest neighbors for each of xj , 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 + log k) · (logN)) + N · k2 · (d + log k), 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 {xj} for an arbitrary point x 2 Rd. The cost of each such query is
proportional to T · (d · (log d) + log(N/k) · k · (d + log k)), 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 certain types of distributions of {xj}, and illustrate its performance via several numerical examples.