<p>A cheap approximate solution using a "locality-sensitive hash" would be to convert each point to it's bit interleaved form:</p>

<p>[xxx,yyy,zzz] -> xyzxyzxyz</p>

<p>then radix sort for preprocessing. </p>

<p>Pick your point to query on and go $k$ points in both directions to get a size $2k$ set; then take the $kth$ nearest to your point. Also see <a href="http://compgeom.com/~piyush/papers/tvcg_stann.pdf" rel="nofollow">this paper</a> by Connor and Kumar.</p>

<p>Also see <a href="http://www.cs.ucsb.edu/~suri/cs235/Rlist/wellSepPairDecom.pdf" rel="nofollow">this paper</a> by Callahan and Kosaraju.</p>

CC BY-SA 3.0
2011-11-10T22:00:42.767Z
2011-11-10T22:09:36.657Z
2011-11-10T22:09:36.657Z
Chad Brewbaker
<p>Here is a simple trick that might be useful. Consider a random sample that picks every point with probability 1/k. It is easy to verify that with good probability exactly one of your k nearest neighbor would be in the sample. Compute the nearest-neighbor in the sample. Repeat this O( k log n) times. With high probability the k nearest points in the $O(k \log n)$ points computed are the k nearest neighbors to your query. Thus, finding the k nearest neighbor, is equivalent to doing $O( k \log n)$ nearest neighbor queries.</p>

<p>In short, give me a fast data-structure for answering nearest neighbor queries, and I would be happy to give you a fast data-structure of k-nearest neighbor. </p>

CC BY-SA 3.0
2011-11-10T17:36:42.817Z
Nice trick. It should be okay to re-use the samples for different query points, too, right? So to calculate the $k$-nearest-neighbor for each point in the set, I only need to build the data structure $O(k \log n)$ times.
Danica
CC BY-SA 3.0
2011-11-10T18:26:33.443Z
Reusing the samples is tricky, because then you're requiring that a fixed sample works for ANY query (the quantification is flipped) and so the probabilities would change. The general idea would then be to construct a set of samples of larger size (this depends on the #queries) and use them, if that's an issue.
Suresh Venkat
CC BY-SA 3.0
2011-11-10T19:56:46.123Z
@SureshVenkat Ah, of course. I'll sit down and figure out the actual probabilities. Thanks everyone!
Danica
CC BY-SA 3.0
2011-11-10T20:40:19.033Z
If you do $O( k \log (1/\delta))$ samples, then each query succeeds with probability $\geq 1-\delta$. Notice, that this trick is slightly better than it look at first glimpse - you have $O(k \log n)$ samples, each one of them of size $O( n/k)$ (with high probability if $k$ is not too large). Which means better query time for each of the samples.
Sariel Har-Peled
CC BY-SA 4.0
2022-09-30T10:56:55.267Z
@Sariel Har-Peled Is it possible to solve the asked problem in $o(k \log n)$ time?
Shi
CC BY-SA 4.0
2022-10-07T01:13:13.447Z
@Shi for low dimensional Euclidean space - yes. I think O( log n + k) is known using near linear space using approximate Voronoi diagrams. In general,  I dont think anything useful is known....
Sariel Har-Peled
CC BY-SA 3.0
2011-11-10T04:13:19.443Z
2011-11-10T04:13:19.443Z
Sariel Har-Peled
<p>For a machine learning application, my group needs to calculate the Euclidean distance to the $k$th nearest neighbor in a set $X$ for each $x \in (X \cup Y) \subset \mathbb R^d$ (for $d$ between 5 and about 100, and $|X| \approx |Y|$ a few hundred up to a few million). We're currently using either the brute-force $O(d \lvert X \rvert \lvert X \cup Y \rvert)$ approach or the obvious one with a kd-tree on $X$, which when $d$ is high and $|X|$ is relatively low doesn't ever win. (Everything is in-memory.)</p>

<p>It seems like there must be a better way than brute-force, though -- at least one that takes advantage of the triangle inequality, or maybe with locality-sensitive hashes. A reasonably tight approximation is also potentially okay.</p>

<p>The research I've been able to find seems to focus on the problem of finding the single nearest neighbor (or one that is approximately the nearest). Does the problem I'm looking for go by some other name, or is there a connection to a related problem that I haven't thought of?</p>

CC BY-SA 3.0
2011-11-09T04:25:51.627Z
kd-trees DO take advantage of the triangle inequality. Have you tried using other spacial data partitioning trees? Another thing you might look into (I know nothing of your machine learning algorithm) whether the specific points tend to have structure, which might help you in quickly finding hyperplanes and using those in a k-d-like tree instead of the usual median-per-coordinate split which performs poorly in high dimensions.
Ross Snider
CC BY-SA 3.0
2011-11-09T05:08:50.927Z
@RossSnider thanks for the suggestions. And sure, KD trees use the triangle inequality, but I was thinking of something that would be faster than brute force. :)  What other kinds of spatial data partitioning trees would you recommend? Of [Wikipedia's list](http://en.wikipedia.org/wiki/Template:CS_trees) only maybe vp-trees seem applicable, and they don't seem like they'd be better than kd-trees for Euclidean distance. And I'll think about if there's a better problem-specific way to define separating hyperplanes, but one doesn't come to mind.
Danica
CC BY-SA 3.0
2011-11-09T05:21:30.883Z
I guess I was hoping that the fact that we know we're evaluating this for all of $X$ (as well as other points) would allow for some kind of help in the algorithm. I'm not sure that's the case, though.
Danica
CC BY-SA 3.0
2011-11-09T06:48:53.507Z
what is $k$ typically in your applications ?
Suresh Venkat
CC BY-SA 3.0
2011-11-09T14:50:37.230Z
@SureshVenkat We usually use a $k$ of about 3, sometimes a little larger.
Danica
<reference-request><cg.comp-geom><near-neighbors>
Calculating the distance to the kth nearest neighbor for all points in the set
Danica
# Calculating the distance to the kth nearest neighbor for all points in the set

(Asked by: username_0 on 2011-11-09)

For a machine learning application, my group needs to calculate the Euclidean distance to the $k$th nearest neighbor in a set $X$ for each $x \in (X \cup Y) \subset \mathbb R^d$ (for $d$ between 5 and about 100, and $|X| \approx |Y|$ a few hundred up to a few million). We're currently using either the brute-force $O(d \lvert X \rvert \lvert X \cup Y \rvert)$ approach or the obvious one with a kd-tree on $X$, which when $d$ is high and $|X|$ is relatively low doesn't ever win. (Everything is in-memory.)

It seems like there must be a better way than brute-force, though -- at least one that takes advantage of the triangle inequality, or maybe with locality-sensitive hashes. A reasonably tight approximation is also potentially okay.

The research I've been able to find seems to focus on the problem of finding the single nearest neighbor (or one that is approximately the nearest). Does the problem I'm looking for go by some other name, or is there a connection to a related problem that I haven't thought of?

**Tags:** reference-request, cg.comp-geom, near-neighbors

> **Comments:**
> **username_1**: kd-trees DO take advantage of the triangle inequality. Have you tried using other spacial data partitioning trees? Another thing you might look into (I know nothing of your machine learning algorithm) whether the specific points tend to have structure, which might help you in quickly finding hyperplanes and using those in a k-d-like tree instead of the usual median-per-coordinate split which performs poorly in high dimensions.  
> **username_0**: @RossSnider thanks for the suggestions. And sure, KD trees use the triangle inequality, but I was thinking of something that would be faster than brute force. :)  What other kinds of spatial data partitioning trees would you recommend? Of [Wikipedia's list](http://en.wikipedia.org/wiki/Template:CS_trees) only maybe vp-trees seem applicable, and they don't seem like they'd be better than kd-trees for Euclidean distance. And I'll think about if there's a better problem-specific way to define separating hyperplanes, but one doesn't come to mind.  
> **username_0**: I guess I was hoping that the fact that we know we're evaluating this for all of $X$ (as well as other points) would allow for some kind of help in the algorithm. I'm not sure that's the case, though.  
> **username_2**: what is $k$ typically in your applications ?  
> **username_0**: @SureshVenkat We usually use a $k$ of about 3, sometimes a little larger.  

---

## 2 answers

### Answer by username_4 on 2011-11-10. Score: 10 | Accepted answer

Here is a simple trick that might be useful. Consider a random sample that picks every point with probability 1/k. It is easy to verify that with good probability exactly one of your k nearest neighbor would be in the sample. Compute the nearest-neighbor in the sample. Repeat this O( k log n) times. With high probability the k nearest points in the $O(k \log n)$ points computed are the k nearest neighbors to your query. Thus, finding the k nearest neighbor, is equivalent to doing $O( k \log n)$ nearest neighbor queries.

In short, give me a fast data-structure for answering nearest neighbor queries, and I would be happy to give you a fast data-structure of k-nearest neighbor.

> **Comments:**
> **username_0**: Nice trick. It should be okay to re-use the samples for different query points, too, right? So to calculate the $k$-nearest-neighbor for each point in the set, I only need to build the data structure $O(k \log n)$ times.  
> **username_2**: Reusing the samples is tricky, because then you're requiring that a fixed sample works for ANY query (the quantification is flipped) and so the probabilities would change. The general idea would then be to construct a set of samples of larger size (this depends on the #queries) and use them, if that's an issue.  
> **username_0**: @SureshVenkat Ah, of course. I'll sit down and figure out the actual probabilities. Thanks everyone!  
> **username_4**: If you do $O( k \log (1/\delta))$ samples, then each query succeeds with probability $\geq 1-\delta$. Notice, that this trick is slightly better than it look at first glimpse - you have $O(k \log n)$ samples, each one of them of size $O( n/k)$ (with high probability if $k$ is not too large). Which means better query time for each of the samples.  
> **username_5**: @username_4 Is it possible to solve the asked problem in $o(k \log n)$ time?  
> **username_4**: @username_5 for low dimensional Euclidean space - yes. I think O( log n + k) is known using near linear space using approximate Voronoi diagrams. In general,  I dont think anything useful is known....  

---

### Answer by username_3 on 2011-11-10. Score: 3

A cheap approximate solution using a "locality-sensitive hash" would be to convert each point to it's bit interleaved form:

[xxx,yyy,zzz] -> xyzxyzxyz

then radix sort for preprocessing.

Pick your point to query on and go $k$ points in both directions to get a size $2k$ set; then take the $kth$ nearest to your point. Also see [this paper](http://compgeom.com/~piyush/papers/tvcg_stann.pdf) by Connor and Kumar.

Also see [this paper](http://www.cs.ucsb.edu/~suri/cs235/Rlist/wellSepPairDecom.pdf) by Callahan and Kosaraju.


---

