COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

A Randomized Approximate Nearest Neighbors Algorithm
by Osipov, Andrei, Ph.D., Yale University, 2011, 137; 3467911
Abstract (Summary)

We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. Given N points {xj} in [special characters omitted], 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 · k 2 · (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 ∈ [special characters omitted]. 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.

Indexing (document details)
Advisor: Rokhlin, Vladimir
School: Yale University
School Location: United States -- Connecticut
Source: DAI-B 72/10, Dissertation Abstracts International
Subjects: Applied Mathematics, Computer science
Keywords: Approximate nearest neighbors, Euclidean space, Fast random rotations, Randomized algorithm, User-specified integer parameters
Publication Number: 3467911
ISBN: 978-1-124-80611-2
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy