2 Added k-nearest-neighbor tag for increased visibility
| link
1
source | link

how to find the nearest neighbor of a sparse vector

I have about 500 vectors,each vector is a 1500-dimension vector, and almost every vector is very sparse-- I mean only about 30-70 dimension of the vector is not 0。

Now, the problom is that here is a given vetor,also 1500 dimension,and I need to compare it to the 500 vectors to find which of the 500 is the nearest one.(In euclidean distance).

There is no doubt that brute-force method is a solution , but I need to calculate the distance for 500 times ,which takes a long time.

Yesterday I read an article "Object retrieval with large vocabularies and fast spatial matching", it says using inverted index will help,its says: enter image description here enter image description here but after my test, it made almost no sense, imagine a 1500-vector in which 50 of the dimension are not zero, when it comes to another one, they may always have the same dimension that are not zero. In other words, this algorithm can only rule out a little vectors, I still need to compare with many vectors left.

Thank you for your nice that you have read to here, my question is that:

1.will this algorithm make sense?

2.is there any other way to do what I want to do? such as flann or Kd-TREE? but I want the exact accurate nearest neighbor, a approxiate one is not enough