VP træ

VP-træ ( engelsk  vantage-point tree ) er en slags BSP-træ .

Et VP-træ kan bygges til objekter fra et metrisk rum , det vil sige for ethvert sæt, hvor afstanden mellem to vilkårlige elementer i dette sæt er defineret.

Trækonstruktionsprincip

Et af punkterne ("referencepunkt") er taget fra startsættet, og "radius" R for dette punkt er valgt. De resterende punkter er opdelt i to delmængder - med en afstand mindre end R til referencepunktet, og en afstand større end R. I hver af de resulterende delmængder vælges det næste referencepunkt og en ny radius, og så videre, indtil antallet af elementer i hver af de resterende delmængder bliver mindre en vis tærskelværdi.

Referencepunkterne og "radierne" for skillekuglerne er valgt, så træet er så afbalanceret som muligt.

Fordele

I modsætning til et KD-træ , som kun gælder for punkter fra , kan et VP-træ bruges til at finde de nærmeste objekter fra ethvert metrisk rum. Eksempelvis kan Hamming distance bruges som metrik  - så kan VP-træet bruges til at søge på lignende ord fra en ordbog, eller til at søge efter lignende billeder.

Se også

• KD træ
• R-træ
• Binær opdeling af rummet

Litteratur

• Ming Hua, Jian Pei. Rangering af forespørgsler på usikre data . - Springer Science & Business Media, 2011. - S.  60 . — ISBN 978-1-4419-9380-9 .
• Vittorio Castelli, Lawrence D. Bergman. Billeddatabaser: Søgning og genfinding af digitale billeder. - John Wiley & Sons, 2004. - S. 422. - ISBN 978-0-471-46407-5 .

Links

• Parallel algoritme til at finde det nærmeste punkt i en radius