kd-tree сложность алгоритма BBF времени

Question

Я hava 2000 точек с 5000 измерениями, и я хочу получить ближайшего соседа.

Теперь у меня есть некоторые проблемы, может кто-нибудь дать ответ.

1. Люди говорят, что он работает хорошо с высокими размерами. Какова временная сложность?

2. @param max_nn_chks поиск обрезается после изучения этого много записей дерева

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

3. Является ли kdtree лучшими Data Structures для моих данных, чтобы получить ближайший сосед?

Answer 1

1. Временная сложность в основном такая же, как и в ограниченном поиске KD-Tree плюс некоторые мало времени для поддержания очереди приоритетов. Ограниченный алгоритм поиска KD-деревьев должен пересекать дерево на своей полной глубине (log2 от счетчика точек) до предела (максимальное количество листовых узлов/точек, разрешенных для посещения).

2. Да, вы получите неправильный ответ, если предел слишком низок. Вы можете измерить только долю истинного NN в сравнении с количеством найденных узлов листа. Из этого вы можете определить оптимальное значение.

3. Обычно рандомизированное дерево kd-деревьев и иерархическое дерево k-средних лучше всего работают. FLANN предоставляет метод определения того, какой алгоритм использовать (k-средство против рандомизированного kd-дерева леса) и устанавливает для вас оптимальные параметры.

Структура данных также оказывает большое влияние. Если вы знаете, что есть скопления точек, которые находятся близко друг к другу, например, вы можете сгруппировать их в одном узле дерева (например, представить их по центроиду) и ускорить поиск.

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