VP-träd

VP-träd ( engelska  vantage-point tree ) är ett slags BSP-träd .

Ett VP-träd kan byggas för objekt från ett metriskt utrymme , det vill säga för vilken uppsättning som helst där avståndet mellan två valfria element i denna uppsättning är definierat.

Trädkonstruktionsprincip

En av punkterna ("referenspunkt") tas från den initiala uppsättningen och "radien" R för denna punkt väljs. De återstående punkterna delas upp i två delmängder - med ett avstånd mindre än R till referenspunkten, och ett avstånd större än R. I var och en av de resulterande delmängderna väljs nästa referenspunkt och en ny radie, och så vidare, tills antalet element i var och en av de återstående delmängderna blir mindre ett visst tröskelvärde.

Referenspunkterna och "radierna" för uppdelningssfärerna väljs så att trädet är så balanserat som möjligt.

Fördelar

Till skillnad från ett KD-träd , som endast är tillämpligt på punkter från , kan ett VP-träd användas för att hitta de närmaste objekten från valfritt metriskt utrymme. Till exempel kan Hamming-avstånd användas som ett mått  - då kan VP-trädet användas för att söka efter liknande ord från en ordbok, eller för att söka efter liknande bilder.

Se även

• KD träd
• R-träd
• Binär uppdelning av utrymme

Litteratur

• Ming Hua, Jian Pei. Rangordning av frågor på osäkra data . - Springer Science & Business Media, 2011. - S.  60 . — ISBN 978-1-4419-9380-9 .
• Vittorio Castelli, Lawrence D. Bergman. Bilddatabaser: Sök och hämtning av digitala bilder. - John Wiley & Sons, 2004. - P. 422. - ISBN 978-0-471-46407-5 .

Länkar

• Parallell algoritm för att hitta närmaste punkt i en radie