Дерево точек обзора
-
Описание дерева точек обзора
- Дерево точек обзора (VP-tree) разделяет данные в пространстве показателей, выбирая точку обзора и разделяя точки на две части: ближе и дальше от точки обзора.
- Рекурсивное применение процедуры создает древовидную структуру данных, где соседи по дереву близки по пространству.
-
Обобщение: дерево с несколькими точками обзора (MVP-tree)
- Использует более одной точки для разделения каждого уровня.
- Применяется для индексации объектов из больших пространств показателей для запросов поиска сходства.
-
История и развитие
- Питер Янилос и Джеффри Ульман независимо открыли дерево точек обзора.
- Ульман опубликовал метод раньше Янилоса в 1991 году.
- Деревья точек обзора были обобщены на неметрические пространства с использованием дивергенции Брегмана Нильсеном и др.
-
Понимание дерева точек обзора
- Каждый узел содержит входную точку и радиус.
- Левые дочерние элементы находятся внутри круга, правые — за его пределами.
- Дереву нужна только функция расстояния, удовлетворяющая свойствам метрического пространства.
-
Поиск по дереву точек обзора
- Алгоритм поиска рекурсивный, работает с узлом, имеющим точку обзора и пороговое расстояние.
- Если расстояние до точки интереса меньше порогового, выполняется рекурсия к поддереву с точками ближе к точке обзора.
- Аналогичный подход используется для нахождения k ближайших соседей.
-
Преимущества дерева точек обзора
- Избегает этапов предварительной обработки, строит индекс на основе расстояния.
- Простое обновление по сравнению с FastMap, который требует повторного сканирования.
- Гибкость в индексировании объектов с фиксированным числом измерений.
-
Сложность и стоимость
- Временные затраты на построение: O(n log n), поиск ближайшего соседа: O(log n).
- Стоимость пространства: приблизительно n, каждый элемент сохраняется и требуется указатель на узлы-потомки.
- Для создания дерева требуется O(n log n) расстояний, для поиска — O(log n) расстояний.