Computational Mathematics and Scientific Computing Seminar

---

A Randomized Approximate Nearest Neighbors Algorithm

Speaker: Andrei Osipov, Yale University

Location: Warren Weaver Hall 1302

Date: Oct. 26, 2012, 10 a.m.

Synopsis:

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.