Calculating the distance to the kth nearest neighbor for all points in the set

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?

• 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. Nov 9, 2011 at 4:25
• @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 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. Nov 9, 2011 at 5:08
• 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. Nov 9, 2011 at 5:21
• what is $k$ typically in your applications ? Nov 9, 2011 at 6:48
• @SureshVenkat We usually use a $k$ of about 3, sometimes a little larger. Nov 9, 2011 at 14:50

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.

• 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. Nov 10, 2011 at 17:36
• 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. Nov 10, 2011 at 18:26
• @SureshVenkat Ah, of course. I'll sit down and figure out the actual probabilities. Thanks everyone! Nov 10, 2011 at 19:56
• 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. Nov 10, 2011 at 20:40
• @Sariel Har-Peled Is it possible to solve the asked problem in $o(k \log n)$ time?
– Shi
Sep 30, 2022 at 10:56

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

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 by Connor and Kumar.