Entfernung zum $k$ten nächsten Nachbarn effizient für beliebige $k$

Question

Problem. Gegeben $X$ ein endlicher metrischer Kardinalitätsraum $n$, Konstruieren Sie eine Datenstruktur in subquadratischer Zeit, sodass die Abfrage distance to the kth nearest neighbor of x kann in sublinearer Zeit aufgelöst werden (unabhängig von $k$) für beliebig $k \leq n$ Und $x \in X$.

Was ich versucht habe. Ich bin mir der Existenz von Kdtrees, Ball-Trees und Cover-Bäumen bewusst.Unter bestimmten Annahmen (zu denen ich bereit bin) weiß ich, dass diese Strukturen die Abfrage lösen können distance to the nearest neighbor of x in sublinearer Zeit (oft $O(\log(n))$), aber ich konnte keine ähnlichen Ergebnisse für finden $k$nächster Nachbar für beliebig $k$.

Es scheint, dass man oft daran interessiert ist $k$ Werte, die im Vergleich zu klein sind $n$, und dass in diesen Fällen die im vorherigen Absatz erwähnten Algorithmen auf Kosten einer multiplikativen Konstante in der Größenordnung von angepasst werden können $k$.Mein Problem ist, dass ich daran interessiert bin $k$ Werte, die möglicherweise in der Größenordnung von liegen $n$.

Answer 1

Bei einer allgemeinen Metrik ist das nicht möglich.Man kann zum Beispiel beweisen, dass die Antwort mindestens quadratisch dauert $ heta(n)$ Anfragen, im schlimmsten Fall.

Nehmen wir zum Beispiel an, wir hätten es getan $n/2$ Abfragepunkte, die alle sehr weit voneinander entfernt sind, und $n/2$ Zielpunkte.Wir werden danach fragen $n/4$-ter nächster Nachbar jedes Abfragepunkts.Dann jeder $d(q,t)$ kann auf jeden beliebigen Abstand eingestellt werden $[1/2,1]$ für jeden der $n^2/4$ Paare eines Abfragepunkts $q$ und einen Zielpunkt $t$, und jeder kann unabhängig ausgewählt werden, und Sie erhalten eine gültige Metrik.Sie können sich also vorstellen, dass der Abstand durch a angegeben wird $n/2 imes n/2$ Matrix der Entfernungen $d(q,t)$.In $o(n^2)$ Zeit kann man nur lesen $o(n^2)$ der Einträge in dieser Matrix, was nicht ausreicht, um alle Fragen zu beantworten.Sie können dies mit einem kontradiktorischen Argument beweisen:Betrachten Sie welche $q$ wo der Algorithmus gelesen hat $d(q,t)$ für weniger als $n/4$ unterschiedliche Werte von $t$;dann, was auch immer der Algorithmus als ausgibt $n/4$-ter nächster Nachbar $q$, können wir die anderen ungelesenen Abstände so anordnen, dass die Ausgabe des Algorithmus falsch war.