VP-puu

VP-puu ( englanniksi  vantage-point tree ) on eräänlainen BSP-puu .

VP-puu voidaan rakentaa objekteille metriavaruudesta eli mille tahansa joukolle, jossa tämän joukon minkä tahansa kahden elementin välinen etäisyys on määritelty.

Puun rakentamisen periaate

Yksi pisteistä ("vertailupiste") otetaan alkujoukosta ja valitaan tämän pisteen "säde" R. Loput pisteet on jaettu kahteen osajoukkoon - joiden etäisyys vertailupisteeseen on pienempi kuin R ja etäisyys suurempi kuin R. Jokaisessa tuloksena olevassa osajoukossa valitaan seuraava vertailupiste ja uusi säde, ja niin edelleen, kunnes kunkin jäljellä olevan osajoukon elementtien lukumäärästä tulee tietty kynnysarvo pienempi.

Jakopallojen vertailupisteet ja "säteet" valitaan siten, että puu on mahdollisimman tasapainoinen.

Edut

Toisin kuin KD-puu , jota voidaan soveltaa vain pisteisiin , VP-puuta voidaan käyttää lähimpien kohteiden etsimiseen mistä tahansa metriavaruudesta. Esimerkiksi Hamming-etäisyyttä voidaan käyttää mittarina  - sitten VP-puuta voidaan käyttää samankaltaisten sanojen etsimiseen sanakirjasta tai samankaltaisten kuvien etsimiseen.

Katso myös

• KD puu
• R-puu
• Avaruuden binaarinen osiointi

Kirjallisuus

• Ming Hua, Jian Pei. Epävarmojen tietojen sijoituskyselyt . - Springer Science & Business Media, 2011. - S.  60 . — ISBN 978-1-4419-9380-9 .
• Vittorio Castelli, Lawrence D. Bergman. Kuvatietokannat: Digitaalisten kuvien haku ja haku. - John Wiley & Sons, 2004. - S. 422. - ISBN 978-0-471-46407-5 .

Linkit

• Rinnakkaisalgoritmi lähimmän pisteen löytämiseksi säteellä