.png){kind=icon}
.png){kind=icon}
Return
Randomized approximate nearest neighbors algorithm
.png){kind=icon}
OA
AI
DOI：10.1073/pnas.1107769108.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. Given N points {x(j)} in R(d), 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) . (logN)) + 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 x is an element of R(d). The cost of each such query is proportional to T . (d .(log d) vertical bar logdN/ k) . k . (d vertical bar 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:
data mining
dimensionality reduction
fast random rotations
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
P
IF:
9.1
Papers:
10.8W
Citations:
73.5W