# Distance to $k$th nearest neighbor efficiently for arbitrary $k$

Problem. Given $$X$$ a finite metric space of cardinality $$n$$, construct a data structure in subquadratic time such that the query distance to the kth nearest neighbor of x can be resolved in sublinear time (independent of $$k$$) for arbitrary $$k \leq n$$ and $$x \in X$$.

What I have tried. I am aware of the existence of kdtrees, ball-trees, and cover trees. Under some assumptions (which I'm willing to make), I know that these structures can resolve the query distance to the nearest neighbor of x in sublinear time (often $$O(\log(n))$$), but I haven't been able to find similar results for the $$k$$th nearest neighbor for arbitrary $$k$$.

It seems that, often, one is interested in $$k$$ values that are small compared to $$n$$, and that, in those cases, the algorithms mentioned in the previous paragraph can be adapted at the cost of a multiplicative constant of the order of $$k$$. My problem is that I am interested in $$k$$ values that are potentially of the order of $$n$$.

• Can you share the context where you encountered this task? Are you sure this is solvable? I suspect for an arbitrary metric space this task is not solvable in the stated time bounds. Have you looked at BK trees and en.wikipedia.org/wiki/Nearest_neighbor_search? – D.W. Jun 25 '20 at 20:34
• I encountered this task when working with kernel density estimates with adaptive bandwidth. The distance to the kth nearest neighbor of a point can be used to define a density estimate, and sometimes you may want to pick different k's for different points. I have looked at the links you mention. BK trees seem a bit too strict, as I cannot assume that the distance is integer valued, for instance. The other link mentions querying for all the k closest neighbors, whereas I am only interested in the distance to the kth one. I am definitely not sure that this can be done in those time bounds. – luisl Jun 26 '20 at 0:49

For a general metric, you can't. For instance, one can prove it takes at least quadratic time to answer $$\Theta(n)$$ queries, in the worst case.
For instance, suppose we have $$n/2$$ query points that are all very far from each other, and $$n/2$$ target points. We'll ask for the $$n/4$$-th closest neighbor of each query point. Then each $$d(q,t)$$ can be set to any distance in $$[1/2,1]$$ for each of the $$n^2/4$$ pairs of a query point $$q$$ and a target point $$t$$, and each can be chosen independently, and you'll have a valid metric. Thus you can imagine the distance being specified by a $$n/2 \times n/2$$ matrix of distances $$d(q,t)$$. In $$o(n^2)$$ time, you can only read $$o(n^2)$$ of the entries in that matrix, which isn't sufficient to answer all of the queries. You can prove this with an adversarial argument: consider any $$q$$ where the algorithm has read $$d(q,t)$$ for fewer than $$n/4$$ different values of $$t$$; then whatever the algorithm outputs as the $$n/4$$-th nearest neighbor to $$q$$, we can arrange the other unread distances so that the algorithm's output was incorrect.