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?
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.