WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

VP-дерево (англ. vantage-point tree) — разновидность BSP-дерева.

VP-дерево можно построить для объектов из метрического пространства, то есть для любого множества, в котором определено расстояние между любыми двумя элементами этого множества.

Принцип построения дерева

Из первоначального множества берется одна из точек («опорная точка») и выбирается «радиус» R для этой точки. Остальные точки делятся на два подмножества — с расстоянием меньше R до опорной точки, и расстоянием больше R. В каждом из получившихся подмножеств выбирается следующая опорная точка и новый радиус, и т. д., пока количество элементов в каждом из оставшихся подмножеств не станет меньше определенного порогового значения.

Опорные точки и «радиусы» сфер разбиения выбираются так, чтобы дерево получилось максимально сбалансированным.

Преимущества

В отличие от KD-дерева, которое применимо только для точек из , VP-дерево может быть использовано для поиска ближайших объектов из любого метрического пространства. Например, в качестве метрики можно использовать расстояние Хэмминга — тогда VP-дерево можно использовать для поиска похожих слов из словаря, или поиска похожих изображений.

См. также

Литература

  • Ming Hua, Jian Pei. Ranking Queries on Uncertain Data. — Springer Science & Business Media, 2011. — P. 60. ISBN 978-1-4419-9380-9.
  • Vittorio Castelli, Lawrence D. Bergman. Image Databases: Search and Retrieval of Digital Imagery. — John Wiley & Sons, 2004. — P. 422. ISBN 978-0-471-46407-5.


Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии