Дерево обзорной точки
Дерево точек обзора (или дерево VP ) — это метрическое дерево , которое разделяет данные в метрическом пространстве путем выбора положения в пространстве («точка обзора») и разделения точек данных на две части: те точки, которые ближе к точка обзора, чем порог, и те точки, которые таковыми не являются. Рекурсивно применяя эту процедуру для разделения данных на все меньшие и меньшие наборы, создается древовидная структура данных , в которой соседи в дереве, скорее всего, будут соседями в пространстве. [1]
Одно из обобщений называется деревом с несколькими точками обзора (или деревом MVP ): структурой данных для индексации объектов из больших метрических пространств для запросов поиска по сходству . Для разделения каждого уровня используется более одной точки. [2] [3]
История [ править ]
Питер Янилос утверждал, что дерево точки обзора было обнаружено независимо им (Петером Янилосом) и Джеффри Ульманном . [1] Тем не менее, Ульманн опубликовал этот метод раньше Янилоса в 1991 году. [4] Ульман назвал структуру данных метрическим деревом , название VP-дерево было предложено Янилосом. Деревья выгодных точек были обобщены на неметрические пространства с использованием расходимостей Брегмана Нильсеном и др. [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] При этом избегаются этапы предварительной обработки.
- Обновить дерево точек обзора относительно просто по сравнению с подходом FastMap. Для FastMap после вставки или удаления данных наступит момент, когда FastMap придется выполнить повторное сканирование. Это занимает слишком много времени, и неизвестно, когда начнется повторное сканирование. [6]
- Дистанционные методы являются гибкими. Он «способен индексировать объекты, которые представлены как векторы признаков фиксированного числа измерений». [6]
Сложность [ править ]
Затраты времени на построение дерева точек обзора составляют примерно O ( n log n ) . Для каждого элемента дерево опускается на log n уровней, чтобы определить его местонахождение. Однако существует постоянный коэффициент k , где k — количество точек обзора на узел дерева. [3]
Затраты времени на поиск в дереве точек обзора с целью найти одного ближайшего соседа равны O (log n ) . Существует log n уровней, каждый из которых включает k вычислений расстояний, где k — количество точек обзора (элементов) в этой позиции в дереве.
Затраты времени на поиск диапазона точек обзора в дереве, который может быть наиболее важным атрибутом, могут сильно различаться в зависимости от особенностей используемого алгоритма и параметров. статья Брина [3] дает результат экспериментов с несколькими алгоритмами точки зрения с различными параметрами для исследования стоимости, измеряемой в количестве вычислений расстояния.
Затраты места для дерева точек обзора составляют приблизительно n . Каждый элемент сохраняется, и каждому элементу дерева в каждом нелистовом узле требуется указатель на его узлы-потомки. (Подробную информацию об одном из вариантов реализации см. в разделе Brin. Параметр количества элементов в каждом узле играет важную роль.)
При n точках имеется O ( n 2 ) попарные расстояния между точками. Однако для создания дерева точек обзора требуется O ( n log n ) явное вычисление только расстояний , а для поиска требуется только расчет расстояний O (log n ) . Например, если x и y являются точками и известно, что расстояние d ( x , y ) мало, тогда любая точка z , которая находится далеко от x, также обязательно будет почти так же далеко от y, метрического пространства потому что неравенство треугольника дает d ( y , z ) ≥ d ( Икс , z ) - d ( Икс , y ) .
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б Янилос (1993). Структуры данных и алгоритмы поиска ближайших соседей в общих метрических пространствах . Четвертый ежегодный симпозиум ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики Филадельфии, Пенсильвания, США. стр. 311–321.
- ^ Бозкая, Толга; Озсойоглу, Мерал (сентябрь 1999 г.). «Индексирование больших метрических пространств для поисковых запросов по сходству» . АКМ Транс. Система баз данных . 24 (3): 361–404. дои : 10.1145/328939.328959 . ISSN 0362-5915 . S2CID 6486308 .
- ↑ Перейти обратно: Перейти обратно: а б с Брин, Сергей (сентябрь 1995 г.). «Поиск ближайших соседей в больших метрических пространствах» . VLDB '95 Материалы 21-й [так в оригинале] Международной конференции по очень большим базам данных . Цюрих, Швейцария: Morgan Kaufmann Publishers Inc.: 574–584. ISBN 9781558603790 .
- ^ Ульманн, Джеффри (1991). «Выполнение общих запросов близости/сходства с помощью метрических деревьев». Письма об обработке информации . 40 (4): 175–179. дои : 10.1016/0020-0190(91)90074-р .
- ^ Нильсен, Франк (2009). «Деревья точек обзора Брегмана для эффективных запросов ближайших соседей». Труды мультимедиа и опыта (ICME) . IEEE. стр. 878–881.
- ↑ Перейти обратно: Перейти обратно: а б с д и Фу, Ада Вай-чи; Полли Мэй-шуэн Чан; Инь-Лин Чунг; Ю Сан Мун (2000). «Динамическое индексирование vp-дерева для поиска n -ближайших соседей по парным расстояниям» . Журнал VLDB — Международный журнал по очень большим базам данных . Springer-Verlag New York, Inc. Секаукус, Нью-Джерси, США. стр. 154–173. вп . Проверено 2 октября 2012 г.