Ball tree
-
Описание структуры данных
- Ball tree — это структура данных для организации точек в многомерном пространстве.
- Каждая точка разбивается на вложенные шары.
- Шары могут пересекаться, но каждая точка принадлежит одному из них в зависимости от расстояния до центра.
- Листья дерева определяют шары и перечисляют все точки внутри них.
- Каждый узел определяет наименьший шар, содержащий все точки в поддереве.
-
Свойства и сравнение с другими структурами
- Расстояние от точки t до любой точки в шаре B больше или равно расстоянию от t до поверхности шара.
- Ball trees связаны с M-деревьями, но поддерживают только бинарные разбиения.
- M-деревья имеют более глубокую структуру и быстрее обрабатывают запросы.
- Vantage-point деревья также похожи, но используют один шар и оставшиеся данные.
-
Алгоритмы построения
- Существует множество алгоритмов построения ball trees.
- Цель — создать дерево, эффективно поддерживающее запросы нужного типа.
- k-d алгоритм — простейший алгоритм, работающий с полным набором данных.
- Алгоритм разбивает данные по медиане значений в одном измерении.
-
Поиск ближайшего соседа
- Ball trees используются для ускорения поиска ближайшего соседа.
- Алгоритм KNS1 использует свойство расстояния для оптимизации поиска.
- Алгоритм сканирует узлы в глубину, начиная с корня.
- Поддерживается очередь приоритетов для k ближайших точек.
- Если расстояние от t до текущего узла больше, чем у самого дальнего в очереди, узел игнорируется.
- Если узел является листом, сканируются все точки и обновляется очередь.
- Если узел внутренний, алгоритм рекурсивно вызывается для двух детей, начиная с ближайшего к t.
-
Производительность
- Ball trees показывают хорошую производительность в задачах поиска ближайшего соседа, особенно при увеличении числа измерений.
- Лучшая структура данных для конкретного приложения зависит от размерности, количества точек и структуры данных.