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