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
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
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:   <>  |
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <> 
Announcement from: Adi Ditkowski   <>