Войти
A дерево точек обзора (или дерево VP ) - это дерево показателей, которое разделяет данные в метрическом пространстве путем выбора позиции в пространстве ( «точка обзора») и разделение точек данных на две части: те точки, которые ближе к точке обзора, чем порог, и те точки, которые не находятся. Путем рекурсивного применения этой процедуры для разделения данных на все меньшие и меньшие наборы создается древовидная структура данных, где соседи в дереве, вероятно, будут соседями в пространстве.
Одно обобщение - это называется деревом с несколькими точками обзора или деревом MVP : структура данных для индексации объектов из больших метрических пространств для поиск по сходству запросов. Он использует более одной точки для разделения каждого уровня.
Питер Янилос утверждал, что дерево точек обзора было независимо обнаружено им (Питером Янилосом) и Джеффри Ульманном. Тем не менее, Ульманн опубликовал этот метод до Янилоса в 1991 году. Ульманн назвал структуру данных метрическим деревом, название VP-tree было предложено Янилосом. Деревья точек обзора были обобщены на неметрические пространства с использованием расхождений Брегмана Нильсеном и др.
Этот итеративный процесс разбиения аналогичен процессу kd-дерева, но использует круговые (или сферические, гиперсферические и др.), а не прямолинейные перегородки. В двухмерном евклидовом пространстве это можно представить в виде серии кругов, разделяющих данные.
Дерево точек обзора особенно полезно при разделении данных в нестандартном метрическом пространстве на метрическое дерево.
Способ хранения данных в дереве точек обзора можно представить в виде круга. Во-первых, поймите, что каждый узел этого дерева содержит входную точку и радиус. Все левые дочерние элементы данного узла являются точками внутри круга, а все правые дочерние элементы данного узла находятся вне круга. Само дерево не нуждается в какой-либо другой информации о том, что хранится. Все, что ему нужно, это функция расстояния, которая удовлетворяет свойствам метрического пространства .
Дерево точек обзора может использоваться для поиска ближайшего соседа точки. Икс. Алгоритм поиска рекурсивный. На любом данном этапе мы работаем с узлом дерева, имеющим точку обзора v и пороговое расстояние t. Интересующая точка x будет находиться на некотором расстоянии от точки наблюдения v. Если это расстояние d меньше t, тогда используйте алгоритм рекурсивно для поиска поддерева узла, который содержит точки ближе к точке наблюдения, чем порог t; в противном случае выполните рекурсию к поддереву узла, который содержит точки, которые дальше точки обзора, чем порог t. Если рекурсивное использование алгоритма находит соседнюю точку n, расстояние до x которой меньше | t - d | тогда поиск в другом поддереве этого узла не поможет; обнаруженный узел n возвращается. В противном случае поиск в другом поддереве также должен выполняться рекурсивно.
Аналогичный подход работает для поиска k ближайших соседей точки x. В рекурсии другое поддерево ищется для k - k ′ ближайших соседей точки x всякий раз, когда только k ′ (< k) of the nearest neighbors found so far have distance that is less than |t − d|.
Временные затраты на построение дерева Vantage-Point составляют примерно O (n log n). Для каждого элемента дерево спускается на log n уровней, чтобы найти его расположение. Однако существует постоянный коэффициент k, где k - число число точек обзора на узел дерева.
Затраты времени на поиск в дереве точек обзора для поиска единственного ближайшего соседа составляют O (log n). Есть log n уровней, каждый из которых включает k вычислений расстояния, где k - количество точек обзора (элементов) в этой позиции в дереве.
Время, затрачиваемое на поиск в дереве Vantage-Point диапазона, который может быть наиболее важным атрибутом, может сильно различаться в зависимости от специфики используемого алгоритма и параметров. В статье Брина приводятся результаты экспериментов с несколькими алгоритмами точки обзора с различными параметрами для исследования затрат, измеряемых количеством вычислений расстояния.
Стоимость места для дерева Vantage-Point составляет примерно n. Каждый элемент сохраняется, и каждый элемент дерева в каждом нелистовом узле требует указателя на его дочерние узлы. (Подробнее об одном варианте реализации см. У Брина. Параметр количества элементов в каждом узле играет важную роль.)
Обратите внимание, что для некоторых инструментов метрического пространства требуется матрица значений попарного расстояния, стоимость которых составляет O (n), но это не требуется для деревьев Vantage-Point.
