1
$\begingroup$

This is a question from theory community, but I came across this issue in a practical problem. So just have this in mind.

I have a set of real vectors:

$$ S = \lbrace v_1, \dots, v_n \rbrace $$ $v_i \in \mathbb{R}^d$ where $d \approx 100$. Typically the size of this set, $n$ is around 20,000,000:

In practice if I have $v_1$ and $v_2$, I can find the distances between them (say using Euclidean distance).
Consider a different problem: I have $v_i \in S$ and I want to find all of the $k$ ($\approx 20$) closest vectors to $v_i$ in the $S$.

Any efficient algorithm/technique/datastructure for this purpose?

I am interested in either piratical solutions and theoretical results. Even if you have approximate solutions I am interested in.

Update: Here is a similar question I came across but I think they are different: Calculating the distance to the kth nearest neighbor for all points in the set

$\endgroup$
3
  • $\begingroup$ “I want to find all of the k (≈20) vectors to v_i in the S.” Did you mean “I want to find all of the k (≈20) vectors closest to v_i in the S”? $\endgroup$ – Tsuyoshi Ito Nov 19 '14 at 21:53
  • $\begingroup$ If you want to do it only for one shot, you can just scan the points. If you want to do it more than once, then the trick mentioned in the question you link to would work here too. Otherwise, LSH type of tricks should work - it is more of a hacking then a real solution. The following paper by Aiger, Kaplan and Sharir is a good starting point, since they want to solve a related problem, maybe, could be, not sure, etc. research.google.com/pubs/archive/42457.pdf $\endgroup$ – Sariel Har-Peled Nov 21 '14 at 4:35
  • $\begingroup$ What approaches have you considered? We can do a better job of helping you if you tell us in the question what research you've done, what you've already considered, and why you have rejected it. For instance, have you considered using a $k$-d tree? $\endgroup$ – D.W. Nov 25 '14 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.