Calculating the distance to the kth nearest neighbor for all points in the set
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.