A Randomized Approximate Nearest Neighbors Algorithm - A Short Version
Peter W. Jones, Andrei Sergeevich Osipov, Vladimir Abramovich Rokhlin · 2011
Abstract : We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. The algorithm has been tested on a number of artificially generated point distributions. Results of some of those tests are presented. The paper is organized as follows. In the first section, we summarize the mathematical and numerical facts to be used in subsequent sections. In the second section, we describe the Randomized Approximate Nearest Neighbors algorithm (RANN) and analyze its cost and performance. In the third section, we illustrate the performance of the algorithm with several numerical examples.