Tel Aviv University School of Mathematical Sciences Applied Mathematics Seminar Date: Tuesday January 4th, 2011, 15:10 Place: Schreiber Bldg, Room 309 Speaker: Andrei Osipov Yale University Title: A Randomized Approximate Nearest Neighbors Algorithm Abstract: We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional 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) · (log N)) + 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 in 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. Joint work with Vladimir Rokhlin and Peter W. Jones. For information about future seminars, see <http://www.tau.ac.il/~adid/AM_seminar_2010-2011/AM_seminar_2010-2011.html> ______________________________________________________________________ Dr. Adi Ditkowski | Department of Applied Mathematics | School of Mathematical Sciences phone: 972-3-640-5987 | Tel Aviv University, fax : 972-3-640-9357 | Tel Aviv, 69978 Israel email: <adid@post.tau.ac.il> | ______________________________________________________________________ --------------------------------------------------------- Technion Math Net-2 (TECHMATH2) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Adi Ditkowski <adid@post.tau.ac.il>