VP-дерево: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
РоманСузи (обсуждение | вклад) Перенёс ссылки в Викиучебник |
РоманСузи (обсуждение | вклад) дополнение |
||
Строка 15: | Строка 15: | ||
* [[R-дерево]] |
* [[R-дерево]] |
||
* [[Двоичное разбиение пространства]] |
* [[Двоичное разбиение пространства]] |
||
== Литература == |
|||
* {{книга |
|||
| автор = Ming Hua, Jian Pei |
|||
| заглавие = Ranking Queries on Uncertain Data |
|||
| издательство = Springer Science & Business Media |
|||
| год = 2011 |
|||
| pages = 60 |
|||
| isbn = 978-1-4419-9380-9 |
|||
| ref = Hua, Pei |
|||
}} |
|||
* {{книга |
|||
| автор = Vittorio Castelli, Lawrence D. Bergman |
|||
| заглавие = Image Databases: Search and Retrieval of Digital Imagery |
|||
| издательство = John Wiley & Sons |
|||
| год = 2004 |
|||
| pages = 422 |
|||
| isbn = 978-0-471-46407-5 |
|||
| ref = Castelli, Bergman |
|||
}} |
|||
== Ссылки == |
== Ссылки == |
Версия от 07:32, 28 декабря 2015
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.
Ссылки
Для улучшения этой статьи желательно:
|