1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – D.W. Jun 25 '20 at 20:34
  • $\begingroup$ 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. $\endgroup$ – luisl Jun 26 '20 at 0:49
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. This leaves open the question of whether one can do better than quadratic when the space is, e.g., Euclidean (of reasonable dimension). $\endgroup$ – luisl Jun 26 '20 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.