VP fa

A VP-fa ( angolul  vantage-point tree ) egyfajta BSP-fa .

Egy VP-fa építhető egy metrikus tér objektumaihoz , azaz bármely halmazhoz, amelyben a halmaz bármely két eleme közötti távolság definiálva van.

Fa építési elv

Az egyik pontot („referenciapont”) a kezdeti halmazból veszik, és ennek a pontnak az „R sugarát” választják ki. A fennmaradó pontokat két részhalmazra osztjuk – a referenciaponttól R-nél kisebb távolsággal és R-nél nagyobb távolsággal. Az eredményül kapott részhalmazok mindegyikében kiválasztásra kerül a következő referenciapont és egy új sugár, és így tovább, amíg a fennmaradó részhalmazok elemeinek száma egy bizonyos küszöbérték alá csökken.

A particionáló gömbök referenciapontjait és "sugarait" úgy választjuk meg, hogy a fa a lehető legkiegyensúlyozottabb legyen.

Előnyök

A KD-fától eltérően , amely csak a -ból származó pontokra alkalmazható , a VP-fa bármely metrikus térből használható a legközelebbi objektumok megkeresésére. Például a Hamming-távolság használható mérőszámként  – ekkor a VP-fával lehet hasonló szavakat keresni egy szótárban, vagy hasonló képeket keresni.

Lásd még

• KD fa
• R-fa
• A tér bináris particionálása

Irodalom

• Ming Hua, Jian Pei. A bizonytalan adatokra vonatkozó lekérdezések rangsorolása . - Springer Science & Business Media, 2011. -  60. o . — ISBN 978-1-4419-9380-9 .
• Vittorio Castelli, Lawrence D. Bergman. Képadatbázisok: Digitális képek keresése és visszakeresése. - John Wiley & Sons, 2004. - P. 422. - ISBN 978-0-471-46407-5 .

Linkek

• Párhuzamos algoritmus a sugár legközelebbi pontjának megtalálására