Эффективное расстояние до $k$-го ближайшего соседа для произвольного $k$

Question

Проблема. Данный $X$ конечное метрическое пространство мощности $n$, постройте структуру данных за субквадратичное время так, чтобы запрос distance to the kth nearest neighbor of x можно решить за сублинейное время (независимо от $к$) для произвольного $k \leq n$ и $x \в X$.

То, что я пробовал. Мне известно о существовании kd-деревьев, шаровых деревьев и покровных деревьев.При некоторых предположениях (которые я готов сделать) я знаю, что эти структуры могут решить запрос. distance to the nearest neighbor of x в сублинейное время (часто $O(\log(n))$), но мне не удалось найти аналогичные результаты для $к$-й ближайший сосед для произвольного $к$.

Кажется, что часто человека интересуют $к$ значения, которые малы по сравнению с $n$, и что в этих случаях алгоритмы, упомянутые в предыдущем параграфе, могут быть адаптированы за счет мультипликативной константы порядка $к$.Моя проблема в том, что мне интересно $к$ значения, потенциально имеющие порядок $n$.

Answer 1

Для общей метрики это невозможно.Например, можно доказать, что для ответа требуется не менее квадратичного времени. $\Тета(n)$ запросы, в худшем случае.

Например, предположим, что у нас есть $n/2$ точки запроса, которые находятся очень далеко друг от друга, и $n/2$ целевые точки.Мы попросим $n/4$-й ближайший сосед каждой точки запроса.Затем каждый $d(q,t)$ можно установить на любое расстояние $[1/2,1]$ для каждого из $n^2/4$ пары точек запроса $q$ и целевая точка $т$, и каждый из них можно выбрать независимо, и вы получите действительную метрику.Таким образом, вы можете представить, что расстояние определяется $n/2 imes n/2$ матрица расстояний $d(q,t)$.В $о(п^2)$ время, ты можешь только читать $о(п^2)$ записей в этой матрице, чего недостаточно для ответа на все запросы.Вы можете доказать это с помощью состязательного аргумента:рассмотреть любой $q$ где алгоритм прочитал $d(q,t)$ менее чем за $n/4$ разные значения $т$;тогда независимо от того, что алгоритм выводит в качестве $n/4$-й ближайший сосед $q$, мы можем расположить другие непрочитанные расстояния так, чтобы выходные данные алгоритма были неверными.