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

<p>I have a set of real vectors: </p>

<p>$$
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: </p>

<p>In practice if I have $v_1$ and $v_2$, I can find the distances between them (say using Euclidean distance).<br>
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$. </p>

<p>Any efficient algorithm/technique/datastructure for this purpose? </p>

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

<p>Update: Here is a similar question I came across but I think they are different: <a href="https://cstheory.stackexchange.com/questions/8875/calculating-the-distance-to-the-kth-nearest-neighbor-for-all-points-in-the-set?rq=1">Calculating the distance to the kth nearest neighbor for all points in the set</a> </p>

CC BY-SA 3.0
2014-11-19T21:53:34.933Z
“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”?
Tsuyoshi Ito
CC BY-SA 3.0
2014-11-21T04:35:08.677Z
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.

http://research.google.com/pubs/archive/42457.pdf
Sariel Har-Peled
CC BY-SA 3.0
2014-11-25T08:26:53.510Z
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?
D.W.
<ds.algorithms><approximation-algorithms><cg.comp-geom><linear-algebra>
k closest points that belong to a set
Daniel
# k closest points that belong to a set

(Asked by: username_0 on 2014-11-19)

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](https://cstheory.stackexchange.com/questions/8875/calculating-the-distance-to-the-kth-nearest-neighbor-for-all-points-in-the-set?rq=1)

**Tags:** ds.algorithms, approximation-algorithms, cg.comp-geom, linear-algebra
> **Comments:**
> **username_1**: “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”?  
> **username_2**: 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.  http://research.google.com/pubs/archive/42457.pdf  
> **username_3**: 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?  

---

## 0 answers

