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

Лоптасто или метричко стабло (енгл. Ball tree), је структура података за партиционисање меморије у мултидимензионом простору. Назив долази због партиционисања меморије у збијене сетове хиперсфера зване лопте. Резултат је да структура података има карактеристике које је чине корисним за велики број апликација, као, на пример, за претраживање најближег суседа.

Информациони опис

Лоптасто стабло је бинарно стабло у коме сваки чвор дефинише D-димензиону хиперсферу, или лопту, која садржи подскуп тачака које треба претражити. Сваки чвор стабла партиционише меморију у дисјунктне сетове који су повезани са различитим лоптама. Док се лопте медусобно могу укрстити, сваки део меморије је додељен једној или другој лопти приликом партиционисања, према његовој удаљености од центра лопте. Сваки лист у стаблу дефинише сферу и нумерише све делове меморије у тој лопти.

Сваки чвор у стаблу дефинише најмању лопту која садржи све делове меморије у свом подстаблу. Ово омогућује да за тест тачку т, растојање до сваке тачке у лопти Б у дрвету је већа или једнака удаљености $t$ од лопте. Формално:

$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}}$

Где је $D^{B}(t)$ минимално могуће растојање од било које тачке у лопти Б до неке тачке т.

Лопта стабла су у релацији са M-стаблом, али подржавају само бинарне поделе, док се у M-стаблу сваки ниво може делити од $m$ до $2m$ пута, па долази до мање дубине структуре стабла. M-стабло такође одрзава раздаљину од родитеља, како би убрзао позиве.

Конструкција

Неколико конструктивних алгоритама лопта стабала су доступни. Циљ таквих алгоритама је да направе стабла која ће ефикасно подржати упите жељених типова(нпр. најближи сусед) у просечном случају. Специфични критеријум је идеално дрво које зависи од типа питања на које се одговара и дистрибуцију фундаменталних података. Ипак, генерално, ефикасно дрво је оно које минимизује обим својих унутрасњих чворова. У пракси се показује да је ово теско извести, али постоји неколико хеуристика које добро деле податке. Генерално, треба наци средину измеду цене за прављење стабла и ефикасности која је остварена.

У овој секцији бице описани најпростији од ових алгоритама. Детаљнији опис дао је Степхен Омохундро.

к-д Конструкциони алгоритам

Најједноставнија процедура је "к-д Конструкциони алгоритам", аналогно са свим процесима који се користе за конструкцију К-D стабла. Ово је офф-лине алгоритам, односно, алгоритам који оперише на целом скупу података одједном. Стабло је изградено одозго надоле рекурзивно делећи податке у два скупа. Делови су изабрани користећи једну димензију са највећом поделом таћака, и скуповима подељењим средњом вредношћу свих тацака. Претрага свих подела за сваки унутрасњи чвор захтева линеарно време по броју узорака који се налазе у том чвору, дајући алгоритам са временском слозеносцу $O(n\,lg\,n)$, где је н број података.

Псеудокод

   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

Тразење најближег суседа

Битна ставка коју лопта стабла раде је убрзавање тражења најближег суседа, у којем треба наци к тачака у стаблу, која су најближа одређеној тацки на одређеном растојању. Једноставан алгоритам, зван КНС1 користи та растојања. Ако алгоритам тражи структуру података са тест тачком т и вец има неку тачку п која је најблиза тачки т, онда це свако стабло ција је лопта даља од т него од п бити игнорисано до краја преграге.

Опис

Лопта стабло је алгоритам најближег суседа који испитује чворове у дубину, почињуци из корена. Приликом претраге, алгоритам ради на основу реда са приоритетом(који је често имплементиран преко хипа (структура података), означава Q, од к најблизих тацака које је до тада просао. На сваком цвору Б, мозе извршити једну од три операције, пре него што конацно врати промењену верзију приоритета.

1. Ако је растојање од тест тачке т до тренутног чвора Б веца од најдаље тачке у Q, игнориси Б и врати Q.
2. Ако је Б лист стабла, прођи кроз све тачке нумерисане у Б , и измени редослед најближег суседа. I врати нови редослед.

1. Ако је Б унутрашњи чвор, позови алгоритам рекурзивно за децу чвора Б, тражеци дете чији је центар ближи тацки т.

Врати редослед после сваког од ових позива у којем је промењен редослед.

Псеудоцоде

   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

Перформансе

У поређењу са неколико других структура података, лопта стабла су показала добар рад на проблему најближег суседа, посебно када број димензија расте. Ипак, најбоља структура за одређену апликацију зависи од димензије, броја података, и структуре података.