Distance sur $k$th voisin le plus proche efficacement pour arbitraire $k$

Question

Problème. Compte tenu de $X$ finie la métrique de l'espace de cardinalité $n$, de construire une structure de données dans subquadratic que la requête distance to the kth nearest neighbor of x peut être résolu en sublinéaire temps (indépendant de $k$) pour arbitraire $k \leq n$ et $x \in X$.

Ce que j'ai essayé. Je suis conscient de l'existence de kdtrees, ball-arbres, et couvrent les arbres.Sous certaines hypothèses (que je suis prête à faire), je sais que ces structures peuvent résoudre la requête distance to the nearest neighbor of x dans sublinéaire temps (souvent $O(\log(n))$), mais je n'ai pas été en mesure de trouver des résultats similaires pour le $k$th voisin le plus proche pour arbitraire $k$.

Il semble que, souvent, on s'intéresse à $k$ les valeurs qui sont petites par rapport à $n$, et que, dans ces cas, les algorithmes mentionnés dans le paragraphe précédent peut être adapté au prix d'une constante multiplicative de l'ordre de $k$.Mon problème est que je suis intéressé à $k$ les valeurs qui sont potentiellement de l'ordre de $n$.

Answer 1

Pour un général de métrique, vous ne pouvez pas.Par exemple, on peut prouver, il faut au moins quadratique du temps à répondre $ heta(n)$ les requêtes, dans le pire des cas.

Par exemple, supposons que nous avons $n/2$ requête points qui sont tous très éloignés les uns des autres, et $n/2$ points cibles.Nous allons demander l' $n/4$-ème plus proche voisin de chaque point de requête.Ensuite, chaque $d(q,t)$ peut être réglé à n'importe quelle distance dans $[1/2,1]$ pour chacun des $n^2/4$ paires d'un point de requête $q$ et d'un point cible $t$, et chacun d'eux peut être choisi de manière indépendante, et vous aurez un valide métrique.Ainsi, vous pouvez imaginer la distance spécifiée par un $n/2 imes n/2$ matrice de distances $d(q,t)$.Dans $o(n^2)$ temps, vous pouvez lire la $o(n^2)$ les entrées dans cette matrice, ce qui n'est pas suffisant pour répondre à toutes les requêtes.Vous pouvez le prouver avec un argument contradictoire:examiner toute $q$ où l'algorithme a lire $d(q,t)$ pour moins de $n/4$ les différentes valeurs de $t$;alors, quel que soit l'algorithme de sorties comme les $n/4$-th voisin le plus proche à $q$, nous pouvons organiser les autres non lus distance de sorte que l'algorithme de sortie était incorrecte.