Поиск KNN с подписанными метриками

Я ищу библиотеку С++, которая позволяет эффективно находить k-ближайших соседей точки в наборе точек, используя псевдонорму в квадрате:
введите здесь описание изображения

где моя третья координата может иметь или не иметь знак минус в квадрате нормы. В качестве альтернативы я могу рассмотреть четырехмерное пространство, где третий компонент всегда имеет положительный знак, а четвертый всегда отрицательный.

В документации библиотеки ANN указано, что она может использовать любую метрику Минковского. Показанная выше метрика является определением метрики Минковского (в смысле Wolfram Mathworld , но не в смысле ИНС). Однако ИНС кажется гибкой и требует только операторов «+» и «-» (документация ANN, стр. 14), но они определяются не для каждого компонента, а глобально.

Кто-нибудь когда-нибудь обобщал ИНС для обработки такого случая? Это тривиально? Разве это не портит kd-tree? Существует ли для этого другая библиотека?

Спасибо!


c++ algorithm knn nearest-neighbor
person nbonneel    schedule 03.12.2012    source источник
comment
Не уточнит ли тот, кто проголосовал за закрытие вопроса по неконструктивной причине? Мой вопрос является целевым, ранее не задавался и принесет пользу сообществу. Я был бы рад отредактировать свой вопрос, если будут сделаны конкретные комментарии, но одно закрытое голосование мало чем поможет. Например, будет ли более подходящим удаление тега c++ и вопрос о том, правильно ли метрика Минкоски обрабатывается структурой Kd-дерева?   -  person nbonneel    schedule 03.12.2012

Ответы (1)


arrow_upward
0
arrow_downward

Норма x2+y2-z2 нарушает некоторые предположения, на которых обычно основан поиск с использованием kd-дерева. Одно из этих предположений состоит в том, что «окрестность» («близость») является некоторым «локальным» свойством, т. е. для данной точки P все точки Q с dist(P,Q) < r имеют координаты в конечном диапазоне вокруг координат P. Таким образом, разбивая набор точек вдоль их координаты могут быть использованы для эффективного поиска. Но для приведенной выше нормы даже для точек Q с dist([0,0,0],Q) = 0 не может быть задано ни одного конечного ящика; точки лежат на бесконечном конусе. Тем не менее, должна быть возможность разработать эффективный алгоритм поиска, использующий структуру «конуса», но kd-дерево не будет работать.

person coproc    schedule 03.12.2012