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