Distância até $k$ésimo vizinho mais próximo de forma eficiente para $k$ arbitrários

Question

Problema. Dado $X$ um espaço métrico finito de cardinalidade $n$, construa uma estrutura de dados em tempo subquadrático tal que a consulta distance to the kth nearest neighbor of x pode ser resolvido em tempo sublinear (independentemente de $k$) para arbitrário $k\leqn$ e $x em X$.

O que eu tentei. Estou ciente da existência de kdtrees, ball-trees e árvores de cobertura.Sob algumas suposições (que estou disposto a fazer), sei que essas estruturas podem resolver a questão distance to the nearest neighbor of x em tempo sublinear (muitas vezes $O(\log(n))$), mas não consegui encontrar resultados semelhantes para o $k$o vizinho mais próximo para arbitrário $k$.

Parece que, muitas vezes, alguém está interessado em $k$ valores que são pequenos em comparação com $n$, e que, nesses casos, os algoritmos mencionados no parágrafo anterior podem ser adaptados ao custo de uma constante multiplicativa da ordem de $k$.Meu problema é que estou interessado em $k$ valores que são potencialmente da ordem de $n$.

Answer 1

Para uma métrica geral, você não pode.Por exemplo, pode-se provar que leva pelo menos um tempo quadrático para responder $ eta(n)$ perguntas, na pior das hipóteses.

Por exemplo, suponha que temos $n/2$ pontos de consulta que estão todos muito distantes uns dos outros, e $n/2$ pontos alvo.Pediremos o $n/4$-ésimo vizinho mais próximo de cada ponto de consulta.Então cada $d(q,t)$ pode ser definido para qualquer distância em $[1/2,1]$ para cada um dos $n^2/4$ pares de um ponto de consulta $q$ e um ponto alvo $t$, e cada um pode ser escolhido independentemente, e você terá uma métrica válida.Assim, você pode imaginar a distância sendo especificada por um $n/2 \vezes n/2$ matriz de distâncias $d(q,t)$.Em $o(n^2)$ tempo, você só pode ler $o(n^2)$ das entradas nessa matriz, o que não é suficiente para responder a todas as consultas.Você pode provar isso com um argumento contraditório:considere qualquer $q$ onde o algoritmo leu $d(q,t)$ por menos de $n/4$ valores diferentes de $t$;então o que quer que o algoritmo produza como o $n/4$-º vizinho mais próximo de $q$, podemos organizar as outras distâncias não lidas para que a saída do algoritmo fique incorreta.