Vantage-точка дерево (или В.П. дерево ) представляет собой метрику дерева , что сегрегируется данные в метрическом пространстве , выбирая положение в пространстве ( «точка зрения») и разделение точек данных на две части: те точки, которые ближе к выгодная точка, чем порог, и те точки, которых нет. Путем рекурсивного применения этой процедуры для разделения данных на все меньшие и меньшие наборы создается древовидная структура данных, где соседи в дереве, вероятно, будут соседями в пространстве. [1]
Одно из обобщений называется деревом с несколькими точками обзора или деревом MVP : структура данных для индексации объектов из больших метрических пространств для поисковых запросов на подобие . Для разделения каждого уровня используется более одной точки. [2] [3]
История
Питер Янилос утверждал, что дерево точки обзора было независимо открыто им (Питером Янилосом) и Джеффри Ульманном . [1] Тем не менее, Ульманн опубликовал этот метод до Ианилоса в 1991 году. [4] Ульманн назвал структуру данных метрическим деревом , имя VP-tree было предложено Янилосом. Деревья точек обзора были обобщены на неметрические пространства с использованием расходимостей Брегмана Нильсеном и др. [5]
Этот итеративный процесс разбиения аналогичен процессу k -d-дерева , но использует круговые (или сферические, гиперсферические и т. Д.), А не прямолинейные разбиения. В двухмерном евклидовом пространстве это можно представить как серию кругов, разделяющих данные.
Дерево точек обзора особенно полезно при разделении данных в нестандартном метрическом пространстве на метрическое дерево.
Понимание дерева точек обзора
Способ хранения данных в дереве точек обзора можно представить в виде круга. [6] Во-первых, поймите, что каждый узел этого дерева содержит входную точку и радиус. Все левые дочерние элементы данного узла - это точки внутри круга, а все правые дочерние элементы данного узла находятся за пределами круга. Самому дереву не нужно знать никакой другой информации о том, что хранится. Все, что ему нужно, - это функция расстояния, которая удовлетворяет свойствам метрического пространства . [6]
Поиск в дереве точек обзора
Дерево точек обзора можно использовать для поиска ближайшего соседа точки x . Алгоритм поиска рекурсивный. На любом данном шаге мы работаем с узлом дерева, имеющим точку обзора v и пороговое расстояние t . Интересующая точка x будет находиться на некотором расстоянии от точки обзора v . Если это расстояние d меньше t, тогда используйте алгоритм рекурсивно для поиска в поддереве узла, который содержит точки ближе к точке обзора, чем порог t ; в противном случае выполните рекурсию к поддереву узла, который содержит точки, которые находятся дальше, чем точка обзора, чем пороговое значение t . Если рекурсивное использование алгоритма находит соседнюю точку n с расстоянием до x , меньшим, чем | т - д | тогда поиск в другом поддереве этого узла не поможет; обнаруженный узел n возвращается. В противном случае поиск в другом поддереве также должен выполняться рекурсивно.
Аналогичный подход работает для поиска k ближайших соседей точки x . В рекурсии другое поддерево ищется k - k ′ ближайших соседей точки x всякий раз, когда только k ′ (< k ) из найденных на данный момент ближайших соседей имеют расстояние меньше, чем | т - д | .
Преимущества дерева точек обзора
- Вместо того, чтобы вывести многомерные точки для домена до построения индекса, мы строим индекс непосредственно на основе расстояния. [6] Это позволяет избежать этапов предварительной обработки.
- Обновить дерево точек обзора относительно легко по сравнению с подходом быстрой карты. Для быстрых карт после вставки или удаления данных наступит время, когда fast-map придется заново сканировать. Это занимает слишком много времени, и неясно, когда начнется повторное сканирование.
- Методы, основанные на расстоянии, гибки. Он «способен индексировать объекты, которые представлены в виде векторов признаков с фиксированным числом измерений» [6].
Сложность
Временные затраты на построение дерева Vantage-Point составляют примерно O ( n log n ) . Для каждого элемента дерево спускается на log n уровней, чтобы найти его размещение. Однако существует постоянный коэффициент k, где k - количество точек обзора на узел дерева. [3]
Временные затраты на поиск в дереве Vantage-Point единственного ближайшего соседа составляют O (log n ) . Существует log n уровней, каждый из которых включает k вычислений расстояния, где k - количество точек обзора (элементов) в этой позиции в дереве.
Временные затраты на поиск диапазона в дереве Vantage-Point, который может быть наиболее важным атрибутом, могут сильно варьироваться в зависимости от специфики используемого алгоритма и параметров. В статье Брина [3] приведены результаты экспериментов с несколькими алгоритмами точки наблюдения с различными параметрами для исследования стоимости, измеряемой числом вычислений расстояния.
Стоимость места для дерева Vantage-Point составляет примерно n . Каждый элемент сохраняется, и каждый элемент дерева в каждом нелистовом узле требует указателя на его дочерние узлы. (Подробнее об одном варианте реализации см. У Брина. Параметр количества элементов в каждом узле играет важную роль.)
Обратите внимание, что для некоторых инструментов метрического пространства требуется матрица значений попарного расстояния, стоимость которой составляет O ( n 2 ) , но это не требуется для деревьев Vantage-Point.
Рекомендации
- ^ a b Yianilos (1993). Структуры данных и алгоритмы поиска ближайшего соседа в общих метрических пространствах (PDF) . Четвертый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики Филадельфия, Пенсильвания, США. С. 311–321. pny93 . Проверено 22 августа 2008 .
- ^ Бозкая, Толга; Озсойоглу, Мерал (сентябрь 1999 г.). «Индексирование больших метрических пространств для поисковых запросов на сходство». ACM Trans. База данных Syst . 24 (3): 361–404. DOI : 10.1145 / 328939.328959 . ISSN 0362-5915 .
- ^ а б в Брин, Сергей (сентябрь 1995 г.). «Поиск ближайшего соседа в больших метрических пространствах» . VLDB '95 Труды 21-й Международной конференции по очень большим базам данных . Цюрих, Швейцария: Morgan Kaufmann Publishers Inc .: 574–584.
- ^ Ульманн, Джеффри (1991). «Удовлетворение общих запросов о близости / сходстве с помощью деревьев показателей». Письма об обработке информации . 40 (4): 175–179. DOI : 10.1016 / 0020-0190 (91) 90074-р .
- ^ Нильсен, Франк (2009). «Деревья точек обзора Брегмана для эффективных запросов ближайшего соседа». Труды мультимедиа и опыта (ICME) . IEEE. С. 878–881.
- ^ а б в г Фу, Ада Вай-чи; Полли Мэй-сюен Чан; Инь-Лин Чунг; Ю Сан Мун (2000). «Динамическое индексирование vp-дерева для поиска n ближайших соседей с заданными попарными расстояниями» . Журнал VLDB - Международный журнал по очень большим базам данных . Springer-Verlag New York, Inc., Секакус, Нью-Джерси, США. С. 154–173. vp . Проверено 2 октября 2012 .