Дерево точек обзора (или дерево VP ) — это метрическое дерево , которое разделяет данные в метрическом пространстве , выбирая положение в пространстве («точка обзора») и разделяя точки данных на две части: те точки, которые ближе к точка обзора, чем порог, и те точки, которые не являются. Путем рекурсивного применения этой процедуры для разделения данных на все более мелкие наборы создается древовидная структура данных , в которой соседи в дереве, вероятно, будут соседями в пространстве. [1]
Одно обобщение называется деревом с несколькими точками обзора или деревом MVP : структура данных для индексации объектов из больших метрических пространств для запросов поиска подобия . Он использует более одной точки для разделения каждого уровня. [2] [3]
Питер Янилос утверждал, что дерево с обзорной площадки было открыто независимо друг от друга им (Питер Янилос) и Джеффри Ульманном . [1] Тем не менее, Ульманн опубликовал этот метод до Янилоса в 1991 году. [4] Ульманн назвал структуру данных метрическим деревом , название VP-дерево было предложено Янилосом. Деревья точек зрения были обобщены на неметрические пространства с использованием дивергенций Брегмана Нильсеном и др. [5]
Этот итеративный процесс разбиения аналогичен процессу k - d дерева , но использует круговые (или сферические, гиперсферические и т. д.), а не прямолинейные разбиения. В двумерном евклидовом пространстве это можно представить как серию окружностей, разделяющих данные.
Дерево точек зрения особенно полезно при разделении данных в нестандартном метрическом пространстве на метрическое дерево.
То, как дерево точек обзора хранит данные, может быть представлено кругом. [6] Во- первых, поймите, что каждый узел этого дерева содержит входную точку и радиус. Все левые дочерние элементы данного узла являются точками внутри круга, а все правые дочерние элементы данного узла находятся вне круга. Самому дереву не нужно знать никакой другой информации о том, что хранится. Все, что ему нужно, это функция расстояния, которая удовлетворяет свойствам метрического пространства . [6]