Дерево точек обзора - Vantage-point tree

А дерево точек обзора (или же Дерево ВП) это метрическое дерево который разделяет данные в метрическое пространство путем выбора позиции в пространстве («точки обзора») и разделения точек данных на две части: те точки, которые находятся ближе к точке обзора, чем порог, и те точки, которые не находятся. Рекурсивно применяя эту процедуру для разделения данных на все меньшие и меньшие наборы, древовидная структура данных создается там, где соседи в дереве могут быть соседями по пространству.[1]

Одно обобщение называется дерево с множеством точек обзора, или же Дерево MVP: а структура данных для индексации объектов из больших метрические пространства за поиск сходства запросы. Он использует более одной точки для разделения каждого уровня.[2][3]

История

Петр Янилос утверждал, что дерево с точки зрения наблюдения было обнаружено независимо им (Петром Янилосом) и Джеффри Ульманн.[1]Пока что, Ульманн опубликовал этот метод до Янилоса в 1991 году.[4]Ульманн назвал структуру данных метрическое дерево, название VP-дерево было предложено Янилосом. Деревья точек обзора были обобщены на неметрические пространства с использованием расходимостей Брегмана Нильсеном и др.[5]

Этот итеративный процесс разбиения аналогичен процессу k-d дерево, но использует круговые (или сферические, гиперсферические и т. д.), а не прямолинейные перегородки. В двумерном евклидовом пространстве это можно представить в виде серии кругов, разделяющих данные.

Дерево точек обзора особенно полезно при разделении данных в нестандартном метрическом пространстве на метрическое дерево.

Понимание дерева точек обзора

Способ хранения данных в дереве точек обзора можно представить в виде круга.[6] Во-первых, поймите, что каждый узел этого дерево содержит входную точку и радиус. Все оставшиеся дети данного узел точки внутри круга и все правильные дочерние элементы данного узел находятся вне круга. В дерево сам по себе не должен знать никакой другой информации о том, что хранится. Все, что ему нужно, это функция расстояния, удовлетворяющая свойствам метрическое пространство.[6]

Поиск в дереве точек обзора

Дерево точек обзора можно использовать для поиска ближайшего соседа точки. Икс. Алгоритм поиска рекурсивный. На любом этапе мы работаем с узлом дерева, имеющим выгодную позицию. v и пороговое расстояние т. Достопримечательность Икс будет на некотором расстоянии от точки обзора v. Если это расстояние d меньше чем т затем используйте алгоритм рекурсивно для поиска поддерева узла, которое содержит точки ближе к точке обзора, чем порог т; в противном случае перейдите к поддереву узла, который содержит точки, которые находятся дальше точки обзора, чем порог т. Если рекурсивное использование алгоритма находит соседнюю точку п с расстоянием до Икс это меньше чем |т − d| тогда поиск в другом поддереве этого узла не поможет; обнаруженный узел п возвращается. В противном случае поиск в другом поддереве также должен выполняться рекурсивно.

Аналогичный подход работает для поиска k ближайшие соседи точки Икс. В рекурсии ищется другое поддерево k − k ′ ближайшие соседи точки Икс когда только k ′ (< k) ближайших соседей, найденных на данный момент, имеют расстояние меньше, чем |т − d|.

Преимущества дерева точек обзора

  1. Вместо того, чтобы вывести многомерные точки для домена перед построением индекса, мы строим индекс непосредственно на основе расстояния.[6] Это позволяет избежать этапов предварительной обработки.
  2. Обновить дерево точек обзора относительно просто по сравнению с подходом быстрой карты. Для быстрых карт после вставки или удаления данных наступит время, когда fast-map придется заново сканировать. Это занимает слишком много времени, и неясно, когда начнется повторное сканирование.
  3. Методы, основанные на расстоянии, гибки. Он «способен индексировать объекты, которые представлены в виде векторов признаков с фиксированным числом измерений».[6]

Сложность

Затраты времени на построение дерева точки наблюдения составляют приблизительно О(п бревно п). Для каждого элемента дерево спускается по бревно п уровни, чтобы найти свое место. Однако есть постоянный фактор k куда k - количество точек обзора на узел дерева.[3]

Затраты времени на поиск в дереве точек обзора для поиска ближайшего соседа составляют О(бревно п). Есть бревно п уровней, каждый из которых включает k расчет расстояний, где k - количество точек обзора (элементов) в этой позиции в дереве.

Временные затраты на поиск диапазона в дереве Vantage-Point, который может быть наиболее важным атрибутом, могут сильно варьироваться в зависимости от специфики используемого алгоритма и параметров. Бумага Брина [3] дает результат экспериментов с несколькими алгоритмами точки обзора с различными параметрами для исследования стоимости, измеренной в количестве вычислений расстояния.

Стоимость места для дерева Vantage-Point составляет приблизительно п. Каждый элемент сохраняется, и каждый элемент дерева в каждом нелистовом узле требует указателя на его дочерние узлы. (Подробнее об одном варианте реализации см. У Брина. Параметр количества элементов в каждом узле играет важную роль.)

Обратите внимание, что для некоторых инструментов метрического пространства требуется матрица значений попарного расстояния, О(п2), но это не требуется для деревьев Vantage-Point.

Рекомендации

  1. ^ а б Янилос (1993). Структуры данных и алгоритмы поиска ближайшего соседа в общих метрических пространствах (PDF). Четвертый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики Филадельфия, Пенсильвания, США. С. 311–321. pny93. Получено 2008-08-22.
  2. ^ Бозкая, Толга; Озсойоглу, Мерал (сентябрь 1999 г.). «Индексирование больших метрических пространств для поисковых запросов схожести». ACM Trans. База данных Syst. 24 (3): 361–404. Дои:10.1145/328939.328959. ISSN  0362-5915.
  3. ^ а б c Брин, Сергей (сентябрь 1995 г.). «Поиск ближайшего соседа в больших метрических пространствах». VLDB '95 Труды 21-й Международной конференции по очень большим базам данных. Цюрих, Швейцария: Morgan Kaufmann Publishers Inc .: 574–584.
  4. ^ Ульманн, Джеффри (1991). «Удовлетворение общих запросов о близости / сходстве с помощью деревьев показателей». Письма об обработке информации. 40 (4): 175–179. Дои:10.1016 / 0020-0190 (91) 90074-р.
  5. ^ Нильсен, Франк (2009). «Деревья точек обзора Брегмана для эффективных запросов ближайшего соседа». Труды мультимедиа и опыта (ICME). IEEE. С. 878–881.
  6. ^ а б c d Фу, Ада Вай-чи; Полли Мэй-сюен Чан; Инь-Лин Чунг; Ю Сан Мун (2000). «Динамическое индексирование vp-tree для п-поиск ближайшего соседа по попарным расстояниям ". Журнал VLDB - Международный журнал по очень большим базам данных. Springer-Verlag New York, Inc., Секакус, Нью-Джерси, США. С. 154–173. вице-президент. Получено 2012-10-02.

внешняя ссылка