Как эффективно найти k ближайших соседей из дерева kd

Question

На самом деле вопрос был задан раньше, но, насколько мне известно, подходящих ответов не было предоставлено.

Я понимаю, как реализовать дерево k-d и как работает поиск ближайшего соседа. Однако даже после осмотра я не могу найти эффективный способ поиска k ближайших соседей очень эффективно с использованием дерева k-d. Я могу только подумать о том, чтобы найти ближайшего соседа и удалить его, и снова повторить процесс k-1 раз, а затем вставить все удаленные узлы обратно в дерево. Но это кажется излишним и полностью бьет цель.

Я просто хочу найти простой способ найти k ближайших соседей, используя k-d tree. Я не ищу онлайн-реализацию или библиотеку, которая позволила бы мне это сделать. Я просто хочу понять логику, а затем сам реализую ее.

Answer 1

Алгоритм на https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search можно рассматривать как оптимизацию «поиска по всему дереву рекурсивно», и оптимизация должна работать, когда поддерево, которое вы собираетесь искать, не может содержать улучшения для текущего лучшего соседа.

Чтобы изменить это, найдите k ближайших соседей, сохраните k узлов, найденных до сих пор, а не только один ближайший узел и отслеживайте расстояние до самого дальнего из этих узлов. Затем решите выполнить поиск поддерева или проигнорировать его, исходя из того, может ли ближайшая точка внутри этого поддерева улучшить улучшение для самого дальнего из этих k соседей.

Вам понадобится структура данных, такая как куча, которая позволяет хранить элементы k, находить элемент с наивысшим значением расстояния, удалять этот элемент и вставлять вновь найденный элемент.