Distancia al $k$ésimo vecino más cercano de manera eficiente para $k$ arbitrarios

Question

Problema. Dado $X$ un espacio métrico finito de cardinalidad $n$, construya una estructura de datos en tiempo subcuadrático tal que la consulta distance to the kth nearest neighbor of x se puede resolver en tiempo sublineal (independiente de $k$) por arbitrario $k\leq n$ y $x \en X$.

Lo que he probado. Soy consciente de la existencia de kdtrees, ball-trees y cover-trees.Bajo algunas suposiciones (que estoy dispuesto a hacer), sé que estas estructuras pueden resolver la consulta. distance to the nearest neighbor of x en tiempo sublineal (a menudo $O(\log(n))$), pero no he podido encontrar resultados similares para el $k$º vecino más cercano para arbitrario $k$.

Parece que, a menudo, uno está interesado en $k$ valores que son pequeños en comparación con $n$, y que, en esos casos, los algoritmos mencionados en el párrafo anterior pueden adaptarse a costa de una constante multiplicativa del orden de $k$.Mi problema es que me interesa $k$ valores que son potencialmente del orden de $n$.

Answer 1

Para una métrica general, no puedes.Por ejemplo, se puede demostrar que se necesita al menos un tiempo cuadrático para responder $ heta(n)$ consultas, en el peor de los casos.

Por ejemplo, supongamos que tenemos $n/2$ puntos de consulta que están muy lejos unos de otros, y $n/2$ puntos objetivo.pediremos el $n/4$-ésimo vecino más cercano de cada punto de consulta.Entonces cada $d(q,t)$ se puede ajustar a cualquier distancia en $[1/2,1]$ para cada uno de los $n^2/4$ pares de un punto de consulta $q$ y un punto objetivo $t$, y cada uno se puede elegir de forma independiente y tendrás una métrica válida.Por lo tanto, puedes imaginar la distancia especificada por un $n/2 \veces n/2$ matriz de distancias $d(q,t)$.En $o(n^2)$ tiempo, solo puedes leer $o(n^2)$ de las entradas de esa matriz, que no es suficiente para responder a todas las consultas.Puedes probar esto con un argumento contradictorio:considerar cualquier $q$ donde el algoritmo ha leído $d(q,t)$ por menos de $n/4$ diferentes valores de $t$;entonces, cualquier cosa que el algoritmo genere como $n/4$-ésimo vecino más cercano a $q$, podemos organizar las otras distancias no leídas para que la salida del algoritmo sea incorrecta.