Лоптасто стабло

Loptasto ili metričko stablo (engl. Ball tree), je struktura podataka za particionisanje memorije u multidimenzionom prostoru. Naziv dolazi zbog particionisanja memorije u zbijene setove hipersfera zvane lopte. Rezultat je da struktura podataka ima karakteristike koje je čine korisnim za veliki broj aplikacija, kao, na primer, za pretraživanje najbližeg suseda.

Informacioni opis

Loptasto stablo je binarno stablo u kome svaki čvor definiše D-dimenzionu hipersferu, ili loptu, koja sadrži podskup tačaka koje treba pretražiti. Svaki čvor stabla particioniše memoriju u disjunktne setove koji su povezani sa različitim loptama. Dok se lopte medusobno mogu ukrstiti, svaki deo memorije je dodeljen jednoj ili drugoj lopti prilikom particionisanja, prema njegovoj udaljenosti od centra lopte. Svaki list u stablu definiše sferu i numeriše sve delove memorije u toj lopti.

Svaki čvor u stablu definiše najmanju loptu koja sadrži sve delove memorije u svom podstablu. Ovo omogućuje da za test tačku t, rastojanje do svake tačke u lopti B u drvetu je veća ili jednaka udaljenosti $t$ od lopte. Formalno:

$D^{Cvor}(t)={\begin{cases}max(|t-B.pivot|-B.radius,D^{B.otac}),&{\text{if }}Cvor\neq Koren\\max(|t-B.pivot|-B.radius,0),&{\text{if }}B=Koren\\\end{cases}}$

Gde je $D^{B}(t)$ minimalno moguće rastojanje od bilo koje tačke u lopti B do neke tačke t.

Lopta stabla su u relaciji sa M-stablom, ali podržavaju samo binarne podele, dok se u M-stablu svaki nivo može deliti od $m$ do $2m$ puta, pa dolazi do manje dubine strukture stabla. M-stablo takođe odrzava razdaljinu od roditelja, kako bi ubrzao pozive.

Konstrukcija

Nekoliko konstruktivnih algoritama lopta stabala su dostupni. Cilj takvih algoritama je da naprave stabla koja će efikasno podržati upite željenih tipova(npr. najbliži sused) u prosečnom slučaju. Specifični kriterijum je idealno drvo koje zavisi od tipa pitanja na koje se odgovara i distribuciju fundamentalnih podataka. Ipak, generalno, efikasno drvo je ono koje minimizuje obim svojih unutrasnjih čvorova. U praksi se pokazuje da je ovo tesko izvesti, ali postoji nekoliko heuristika koje dobro dele podatke. Generalno, treba naci sredinu izmedu cene za pravljenje stabla i efikasnosti koja je ostvarena.

U ovoj sekciji bice opisani najprostiji od ovih algoritama. Detaljniji opis dao je Stephen Omohundro.

k-d Konstrukcioni algoritam

Najjednostavnija procedura je "k-d Konstrukcioni algoritam", analogno sa svim procesima koji se koriste za konstrukciju K-D stabla. Ovo je off-line algoritam, odnosno, algoritam koji operiše na celom skupu podataka odjednom. Stablo je izgradeno odozgo nadole rekurzivno deleći podatke u dva skupa. Delovi su izabrani koristeći jednu dimenziju sa najvećom podelom taćaka, i skupovima podeljenjim srednjom vrednošću svih tacaka. Pretraga svih podela za svaki unutrasnji čvor zahteva linearno vreme po broju uzoraka koji se nalaze u tom čvoru, dajući algoritam sa vremenskom slozenoscu $O(n\,lg\,n)$, gde je n broj podataka.

Pseudokod

   function construct_balltree is
       input: 
           D, an array of data points
       output: 
           B, the root of a constructed ball tree
       if a single point remains then
           create a leaf B containing the single point in D
           return B
       else
           let c be the dimension of greatest spread
           let L,R be the sets of points lying to the left and right of the median along dimension c
           create B with two children: 
               B.pivot = c
               B.child1 = construct_balltree(L),
               B.child2 = construct_balltree(R)
           return B
       end if
   end function

Trazenje najbližeg suseda

Bitna stavka koju lopta stabla rade je ubrzavanje traženja najbližeg suseda, u kojem treba naci k tačaka u stablu, koja su najbliža određenoj tacki na određenom rastojanju. Jednostavan algoritam, zvan KNS1 koristi ta rastojanja. Ako algoritam traži strukturu podataka sa test tačkom t i vec ima neku tačku p koja je najbliza tački t, onda ce svako stablo cija je lopta dalja od t nego od p biti ignorisano do kraja pregrage.

Opis

Lopta stablo je algoritam najbližeg suseda koji ispituje čvorove u dubinu, počinjuci iz korena. Prilikom pretrage, algoritam radi na osnovu reda sa prioritetom(koji je često implementiran preko hipa (struktura podataka), označava Q, od k najblizih tacaka koje je do tada prosao. Na svakom cvoru B, moze izvršiti jednu od tri operacije, pre nego što konacno vrati promenjenu verziju prioriteta.

1. Ako je rastojanje od test tačke t do trenutnog čvora B veca od najdalje tačke u Q, ignorisi B i vrati Q.
2. Ako je B list stabla, prođi kroz sve tačke numerisane u B , i izmeni redosled najbližeg suseda. I vrati novi redosled.

1. Ako je B unutrašnji čvor, pozovi algoritam rekurzivno za decu čvora B, tražeci dete čiji je centar bliži tacki t.

Vrati redosled posle svakog od ovih poziva u kojem je promenjen redosled.

Pseudocode

   function knn_search is
       input: 
           t, the target point for the query
           k, the number of nearest neighbors of t to search for
           Q, max-first priority queue containing at most k points
           B, a node, or ball, in the tree
       output: 
           Q, containing the k nearest neighbors from within B
       if distance(t, B.pivot) ? distance(t, Q.first) then
           return Q unchanged
       else if B is a leaf node then
           for each point p in B do
               if distance(t, p) < distance(t, Q.first) then
                   add p to Q
                   if size(Q) > k then
                       remove the furthest neighbor from Q
                   end if
               end if
           repeat
       else
           let child1 be the child node closest to t
           let child2 be the child node furthest from t
           knn_search(t, k, Q, child1)
           knn_search(t, k, Q, child2)
       end if
   end function

Performanse

U poređenju sa nekoliko drugih struktura podataka, lopta stabla su pokazala dobar rad na problemu najbližeg suseda, posebno kada broj dimenzija raste. Ipak, najbolja struktura za određenu aplikaciju zavisi od dimenzije, broja podataka, i strukture podataka.