Arborele VP

VP-tree ( în engleză  vantage-point tree ) este un fel de arbore BSP .

Un arbore VP poate fi construit pentru obiecte dintr-un spațiu metric , adică pentru orice mulțime în care este definită distanța dintre oricare două elemente ale acestui set.

Principiul construcției arborelui

Unul dintre puncte („punct de referință”) este luat din setul inițial și este selectată „raza” R pentru acest punct. Punctele rămase sunt împărțite în două subseturi - cu o distanță mai mică decât R până la punctul de referință și o distanță mai mare decât R. În fiecare dintre subseturile rezultate, următorul punct de referință și o nouă rază sunt selectate și așa mai departe, până când numărul de elemente din fiecare dintre subseturile rămase devine mai puțin o anumită valoare de prag.

Punctele de referință și „razele” sferelor de compartimentare sunt alese astfel încât arborele să fie cât mai echilibrat posibil.

Beneficii

Spre deosebire de un arbore KD , care este aplicabil numai punctelor din , un arbore VP poate fi folosit pentru a găsi cele mai apropiate obiecte din orice spațiu metric. De exemplu, distanța Hamming poate fi folosită ca măsurătoare  - apoi arborele VP poate fi folosit pentru a căuta cuvinte similare dintr-un dicționar sau pentru a căuta imagini similare.

Vezi și

• Arborele KD
• R-arborele
• Partiționarea binară a spațiului

Literatură

• Ming Hua, Jian Pei. Clasificarea interogărilor pe date incerte . - Springer Science & Business Media, 2011. - P.  60 . — ISBN 978-1-4419-9380-9 .
• Vittorio Castelli, Lawrence D. Bergman. Baze de date de imagini: căutare și regăsire a imaginilor digitale. - John Wiley & Sons, 2004. - P. 422. - ISBN 978-0-471-46407-5 .

Link -uri

• Algoritm paralel pentru găsirea celui mai apropiat punct dintr-o rază