Введение
Дерево точки отсчета (или VP-дерево) — это метрическое дерево, которое разделяет данные в метрическом пространстве, выбирая позицию в пространстве («точка отсчета») и разделяя точки данных на две части: точки, находящиеся ближе к точке отсчета, чем заданный порог, и точки, находящиеся дальше. Рекурсивно применяя эту процедуру для разделения данных на все более мелкие подмножества, создается древовидная структура данных, в которой соседние элементы в дереве с большой вероятностью будут соседними элементами в пространстве. Обобщением является дерево множественных точек отсчета (или MVP-дерево): структура данных для индексации объектов из больших метрических пространств при выполнении запросов на поиск ближайших соседей. Оно использует более одной точки для разделения на каждом уровне.
История
Питер Йианилос утверждал, что дерево точки обзора было открыто независимо им самим и Джеффри Ульманном. Ульман назвал эту структуру данных метрическим деревом, а название VP-дерево предложил Йианилос. Нильсен и другие обобщили деревья точек обзора для неметрических пространств, используя расхождения Брегмана. Этот итеративный процесс разделения аналогичен процессу в k-d дереве, но использует круговые (или сферические, гиперсферические и т.д.) вместо прямоугольных разбиений. В двухмерном евклидовом пространстве это можно представить как последовательность кругов, разделяющих данные. Дерево точки обзора особенно полезно для разделения данных в нестандартном метрическом пространстве на метрическое дерево.
Понимание дерева точки обзора
Способ хранения данных деревом точки обзора может быть представлен в виде круга.
Поиск через дерево-обзор
Дерево точки обзора может быть использовано для поиска ближайшего соседа точки x. Алгоритм поиска рекурсивный. На каждом шаге мы работаем с узлом дерева, имеющим точку обзора v и пороговое расстояние t. Точка интереса x находится на некотором расстоянии от точки обзора v. Если это расстояние d меньше t, то используйте алгоритм рекурсивно для поиска в поддереве узла, содержащего точки, более близкие к точке обзора, чем порог t; иначе – рекурсивно исследуйте поддерево узла, содержащего точки, более удалённые от точки обзора, чем порог t. Если рекурсивное применение алгоритма находит соседнюю точку n с расстоянием до x, которое меньше текущего минимального расстояния, то дальнейший поиск в другом поддереве этого узла не требуется; найденная точка n возвращается. В противном случае другое поддерево также необходимо исследовать рекурсивно. Аналогичный подход применим для поиска k ближайших соседей точки x. В процессе рекурсии другое поддерево исследуется на предмет k − k′ ближайших соседей точки x, когда только k′ (< k) из найденных на данный момент ближайших соседей имеют расстояние меньше текущего минимального расстояния.
Преимущества дерева обзорной точки
Вместо того, чтобы вычислять многомерные точки для области до построения индекса, мы строим индекс непосредственно на основе расстояния. Это позволяет избежать этапов предварительной обработки. Обновление дерева опорных точек относительно просто по сравнению с подходом FastMap. В случае FastMap, после вставки или удаления данных, наступит момент, когда потребуется повторное сканирование всей структуры. Это занимает слишком много времени, и сложно предсказать, когда начнется повторное сканирование. Методы, основанные на расстоянии, обладают гибкостью и позволяют индексировать объекты, представленные в виде векторов признаков фиксированной размерности.
Сложность
Время построения дерева точек обзора составляет приблизительно O(n log n). Для каждого элемента дерево просматривается в глубину на log n уровнях, чтобы определить его местоположение. Однако существует постоянный фактор k, где k – количество точек обзора в каждом узле дерева. Время поиска ближайшего соседа в дереве точек обзора составляет O(log n). Существует log n уровней, каждый из которых включает k вычислений расстояния, где k – количество точек обзора (элементов) в данной позиции дерева. Время поиска диапазона в дереве точек обзора, которое может быть наиболее важной характеристикой, может значительно варьироваться в зависимости от конкретного используемого алгоритма и параметров. В работе Брина представлены результаты экспериментов с несколькими алгоритмами точек обзора и различными параметрами для оценки стоимости, измеряемой в количестве вычислений расстояния. Объём памяти, занимаемый деревом точек обзора, составляет приблизительно n. Каждый элемент хранится, и каждый элемент дерева в каждом нелистовом узле требует указателя на дочерние узлы. (Подробности об одном из вариантов реализации можно найти в работе Brin. Параметр, определяющий количество элементов в каждом узле, играет важную роль.) Для n точек существует O(n²) парных расстояний между точками. Однако создание дерева точек обзора требует явного вычисления только O(n log n) расстояний, а поиск – только O(log n) вычислений расстояния. Например, если x и y – точки и известно, что расстояние d(x, y) мало, то любая точка z, находящаяся далеко от x, также будет почти так же далеко от y, поскольку неравенство треугольника для метрического пространства гласит: d(y, z) ≥ d(x, z) − d(x, y).