Randomized approximate nearest neighbors algorithm
- 20 September 2011
- journal article
- research article
- Published by National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 108 (38) , 15679-15686
Abstract
We present a randomized algorithm for the approximate nearest neighbor problem in d -dimensional Euclidean space. Given N points { x j } in , the algorithm attempts to find k nearest neighbors for each of x j , where k is a user-specified integer parameter. The algorithm is iterative, and its running 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 by-product of the scheme is a data structure, permitting a rapid search for the k nearest neighbors among { x j } for an arbitrary point . 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 { x j } and illustrate its performance via several numerical examples.Keywords
This publication has 9 references indexed in Scilit:
- An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform2011
- A Randomized Approximate Nearest Neighbors Algorithm2010
- Faster dimension reductionCommunications of the ACM, 2010
- The Fast Johnson–Lindenstrauss Transform and Approximate Nearest NeighborsSIAM Journal on Computing, 2009
- A fast randomized algorithm for overdetermined linear least-squares regressionProceedings of the National Academy of Sciences, 2008
- Near-optimal hashing algorithms for approximate nearest neighbor in high dimensionsCommunications of the ACM, 2008
- Randomized algorithms for the low-rank approximation of matricesProceedings of the National Academy of Sciences, 2007
- An optimal algorithm for approximate nearest neighbor searching fixed dimensionsJournal of the ACM, 1998
- Extensions of Lipschitz mappings into a Hilbert space1984