# 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$$.