What are the fast approximations of the closest neighbor?

Question

Let's say I have a huge (several million) list of n vectors, given the new vector, I need to find a pretty close one from the set, but it doesn't have to be the closest. (The closest neighbor is closest and works for n time)

What are the algorithms that can quickly approximate the nearest neighbor due to accuracy?

EDIT: since this is likely to help, I should mention that the data is pretty smooth in most cases, with little chance of being sharp in a random measurement.

Answer 1

There are faster algorithms, and then O (n) to search for the nearest element at an arbitrary distance. See http://en.wikipedia.org/wiki/Kd-tree for more details .

Answer 2

If you are using a high-dimensional vector like SIFT or SURF, or any descriptor used in the multimedia sector, I suggest you consider LSH.

(http://www.cs.princeton.edu/cass/papers/cikm08.pdf) KNN, LSH. LSH, E2LSH (http://www.mit.edu/~andoni/LSH/), MIT, - .

Answer 3

- lsh http://www.mit.edu/~andoni/LSH/ http://www.cs.umd.edu/~mount/ANN/ http://msl.cs.uiuc.edu/~yershova/MPNN/MPNN.htm

Answer 4

(LSH). LSH. . -O LSH ( ). . LSH LSH L2 ().

, 10, kd tree , .