1
$\begingroup$

So imagine I have a $m$ vectors each of dimension $d$. Lets call them, $\vec x_{i}$, with $i = 1, 2, 3, 4, 5, \dots, m$. Now the idea is to find the neighbours of $\vec x_{i}$ (calling them $\vec x_{j}$), within a ball of radius $r$. So, $$ || \vec x_{i} - \vec x_{j} || \le r$$.

Note: $|| \cdots ||$ is the Euclidean norm.

Naively one can compute distance between all the $j$'s for a particular $i$, and then sort them, and keep only the elements which are less than $r$. This is computationally expensive for large $m$ and $d$.

So the question is how can I efficiently compute the neighbours $x_{j}$?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ For small $d$, KD-trees work pretty well. For example scipy has this function that does exactly what you want. There are even better data structures like range trees and ball trees that reduce the worst-case complexity. But you mention large $d$ and, as far as I know, developing spatial data structures that work well in high-dimensional space is very much an unsolved problem. For example KD-trees fall on their face pretty quick for large $d$. $\endgroup$ – Daniel Shapero Oct 6 '20 at 18:03
  • $\begingroup$ @DanielShapero: How good is the performance for $d \approx 20$? I did have a look at this function, but I'm not well verse in trees. $\endgroup$ – sbp Oct 6 '20 at 18:08
  • 1
    $\begingroup$ In my experience, even for a moderately sized $d$ (20 is pushing the limit), the cost of building the tree and performing a query can be relatively inexpensive relative to the cost of one brute-force nearest neighbor query. I'm sure @DanielShapero is correct in general, but you never know until you try it on your data set. $\endgroup$ – Charlie S Oct 6 '20 at 18:25
  • 1
    $\begingroup$ @CharlieS is absolutely right, experimentation is more valuable than the advice of strangers on the internet :D $\endgroup$ – Daniel Shapero Oct 6 '20 at 18:36
  • $\begingroup$ Thanks for the headsup. I'm running some benchmarks. Let's see! $\endgroup$ – sbp Oct 6 '20 at 19:34
2
$\begingroup$

I suspect that you can get away with a subset of the information by making use of the fact that $$ \|x_i-x_j\| = \|x_i-x_k+x_k-x_j\| \ge \|x_i-x_k\| - \|x_k-x_j\|. $$ You can use this in the following way: Say, you want $r=1$. If $x_1$ and $x_2$ are four units away (not neighbors), and $x_2$ and $x_3$ are one unit away, then $x_1$ and $x_3$ are at least three units away -- also not neighbors. I didn't need to compute the distance between $x_1$ and $x_3$ to determine that.

What this means is that it is possible to use this "reverse triangle inequality" to determine neighborship by knowing only a subset of the entries of the distance matrix $$ D_{ij} = \|x_i-x_j\|. $$ The question is: What subset do you need to know to make all determinations? I would not be very surprised if the algorithm to determine the minimal subset is NP, but one could probably come up with a cheaper algorithm that, starting from some subset of entries of $D_{ij}$ determines which entries do not need to be computed, then computes some of the other currently unknown ones, and iterates that until for every entry of $D$ you've either computed its value, or determined that you don't need it.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.