VP strom

VP-tree ( anglicky  vantage-point tree ) je druh BSP-stromu .

VP-strom lze sestavit pro objekty z metrického prostoru , tedy pro jakoukoli množinu, ve které je definována vzdálenost mezi libovolnými dvěma prvky této množiny.

Princip konstrukce stromu

Jeden z bodů („referenční bod“) je převzat z počáteční sady a je vybrán „poloměr“ R pro tento bod. Zbývající body jsou rozděleny do dvou podmnožin – se vzdáleností menší než R k referenčnímu bodu a vzdáleností větší než R. V každé z výsledných podmnožin se vybere další referenční bod a nový poloměr atd., dokud počet prvků v každé ze zbývajících podmnožin se sníží o určitou prahovou hodnotu.

Referenční body a "poloměry" dělicích koulí jsou voleny tak, aby byl strom co nejvyváženější.

Výhody

Na rozdíl od stromu KD , který je použitelný pouze pro body z , lze strom VP použít k nalezení nejbližších objektů z libovolného metrického prostoru. Jako metriku lze použít například Hammingovu vzdálenost  - pak lze VP-strom použít k vyhledávání podobných slov ze slovníku nebo k vyhledávání podobných obrázků.

Viz také

• KD strom
• R-strom
• Binární dělení prostoru

Literatura

• Ming Hua, Jian Pei. Hodnocení dotazů na nejistá data . - Springer Science & Business Media, 2011. - S.  60 . — ISBN 978-1-4419-9380-9 .
• Vittorio Castelli, Lawrence D. Bergman. Obrazové databáze: Vyhledávání a získávání digitálních snímků. - John Wiley & Sons, 2004. - S. 422. - ISBN 978-0-471-46407-5 .

Odkazy

• Paralelní algoritmus pro nalezení nejbližšího bodu v poloměru