VP-дерево () — разновидность BSP-дерева.
VP-дерево можно построить для объектов из метрического пространства, то есть для любого множества, в котором определено расстояние между любыми двумя элементами этого множества.
Принцип построения дерева Из первоначального множества берется одна из точек («опорная точка») и выбирается «радиус» R для этой точки. Остальные точки делятся на два подмножества — с расстоянием меньше R до опорной точки, и расстоянием больше R. В каждом из получившихся подмножеств выбирается следующая опорная точка и новый радиус, и т. д., пока количество элементов в каждом из оставшихся подмножеств не станет меньше определенного порогового значения.
Опорные точки и «радиусы» сфер разбиения выбираются так, чтобы дерево получилось максимально сбалансированным.
Преимущества В отличие от KD-дерева, которое применимо только для точек из , VP-дерево может быть использовано для поиска ближайших объектов из любого метрического пространства. Например, в качестве метрики можно использовать расстояние Хэмминга — тогда VP-дерево можно использовать для поиска похожих слов из словаря, или поиска похожих изображений.
См. также KD-дерево R-дерево Двоичное разбиение пространства
Литература
Ссылки
Параллельный алгоритм поиска ближайшей точки в радиусе
__NOTOC__ Категория:Деревья (структуры данных) Категория:Алгоритмы