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?