Distanza da $ k $ Il vicino più vicino in modo efficiente per arbitrario $ k $

Question

Problema. data $ x $ uno spazio metrico finito di cardinalità $ N $ < / SPAN>, costruire una struttura dati in tempo subquadratico in modo tale che la query distance to the kth nearest neighbor of x può essere risolta in tempo sublineo (indipendente dalla classe $ k $ ) per arbitrario $ K \ Leq N $ e $ x \ in x $ .

Quello che ho provato. Sono consapevole dell'esistenza di kdtrees, palla e alberi di copertura. Sotto alcune ipotesi (che sono disposto a fare), so che queste strutture possono risolvere la query distance to the nearest neighbor of x nel tempo sublinear (spesso $ o (\ log (n)) $ ), ma non sono stato in grado di trovare risultati simili per la $ k $ vicino vicino per arbitrario $ k $ .

Sembra che, spesso, uno sia interessato a $ k $ valori che sono piccoli rispetto a $ N $ < /, e che, in tali casi, gli algoritmi menzionati nel paragrafo precedente possono essere adattati al costo di una costante moltiplicativa dell'ordine di $ k $ . Il mio problema è che sono interessato a $ k $ valori potenzialmente dell'ordine di $ N $ .

Answer 1

Per una metrica generale, non puoi. Ad esempio, si può dimostrare che richiede almeno il momento quadratico per rispondere a $ \ theta (n) $ query, nel caso peggiore.

Ad esempio, supponiamo di avere $ N / 2 $ punti di query che sono tutti molto lontani dall'altro, e $ n / 2 $ Punti di destinazione. Chiederemo la $ N / 4 $ -th vicino vicino a ciascun punto di query. Quindi ogni $ D (q, t) $ può essere impostato su qualsiasi distanza in $ [1 / 2,1] $ per ciascuna delle $ n ^ 2/4 $ paia di un punto di query $ q $ e un punto di destinazione $ T $ , e ognuno può essere scelto in modo indipendente e avrai una metrica valida. Quindi puoi immaginare la distanza specificata da una $ n / 2 \ volte N / 2 $ matrice di distanze $ D ( q, t) $ . In $ o (n ^ 2) $ Ora, è possibile leggere solo $ o (n ^ 2) $ delle voci in quella matrice, che non è sufficiente per rispondere a tutte le query. Puoi dimostrarlo con un argomento contraddittorio: considerare qualsiasi $ q $ dove l'algoritmo ha letto $ d (q, t) $ per meno di $ N / 4 $ valori diversi di $ T $ ; Quindi l'algoritmo uscirà come la $ N / 4 $ -th vicino vicino a $ q $ , noi può organizzare le altre distanze non lette in modo che l'uscita dell'algoritmo fosse errata.