M-strom je dynamicka indexova struktura pro vyhledavani objektu v metrickem prostoru.

Zakladni vlastnosti:

• dynamický algoritmus (podpora vkladani/mazani objektu)
• disk I/O oriented
• realizovan jako graf - strom
• listy obsahuji objekty
• vnitrni uzly obsahuji odkazy na podstromy
• fixni velikost uzlu (~velikost diskoveho bloku)

List:

• obsahuje dvojice (o, d(o,o^p))
  • o - objekt
  • o^p - rodicovsky pivot
  • d(o,o^p) - funkce vzdalenosti

Vnitrni uzel:

• ctverice (p,rc,d(p,pp),ptr)
  • p - pivot
  • Rc - polomer pokryti (covering radius)
  • pp - rodicovsky pivot
  • ptr - ukazatel na podstrom

Vkladani noveho uzlu On:

• zacatek od korene
• najde se takovy uzel, pro ktery novy objekt On spada do polomeru pokryti Rc
• pokud neni, najde se takovy, pro ktery je potreba nejmene zvetsit Rc pr
• pokud je vice spadajicich, vybere se podstrom s pivotem nejbliz novemu objektu
• uzly maji omezenou kapacitu, pri pretecni nastava deleni uzlu

Deleni uzlu N:

• z mnoziny P = (N,On) se vhodnou strategii vyberou dva nove pivoty p1, p2
  • RANDOM - nahodny vyber p1,p2
  • m_RAD - p1, p2 / R1c + R2C je minimalni
  • mM_RAD - p1, p2 / max(R1c,R2C) je minimalni
  • comfirmed / uncomfirmed - p1 je puvodni pivot / vyber dvou novych
    • dve varianty pro kazdou strategii (RANDOM / RANDOM_2)

Range search R(q,r):

• DFS prohledavani s prorezavanim
  • prorezavaji se takove vetve, kde pro kazdy zaznam (p,rc,d(p,pp),ptr) je splneno |d(pp,q) - d(pp,p)| -Rc > r
  • spocte se d(p,q)
  • dale se vetev proreze, pokud d(p,q) > r (1)
• v uzlovych listech se pro kazdy zaznam (o, d(o,o^p))
  • zaznam se ignoruje, pokud d(o^p,q) > r - stejne jako (1)
  • spocte se d(o,q) a overi se zda d(o,q) ⇐ r

k-NN search:

• obdoba R(q,r)
• pouziva se prioritni fronta
  • pro E = (p,rc,d(p,pp),ptr)
  • DminE = max(d(p,q) - Rc, 0)
  • uklada se (E,DminE)
• misto r se pouziva vzdalenost k aktualnimu k-nejlblizsimu objektu

Zakladni vlastnosti:

• urychleni stavby stromu
• nutno znat dopredu celou mnozinu
• mnozina objektu X = (o1 ... on)
• maximalne m prvku/uzel
• dve faze: tvorba M-stromu a optimalizace M-stromu

tvorba M-stromu:

• z X je nahodne vybrano l pivotu (p1,p2 ... pl), obvykle l = m
• kazde x z X je prirazeno nejblizsimu pivotu, vzniknou mnoziny P1 ... Pl
• vznikne nevyvazeny strom, nutna optimalizace

optimalizace M-stromu:

• malo plne uzly
  • podstromy jsou prealokovany k sousednim pivotum, uzel je vymazan
• moc plne podstromy
  • 

dalsi optimalizace:

Zakladni vlastnosti:

• modifikovana vkladaci procedura
• dynamicke, netreba znat celou mnozinu
• nakladnejsi vkladani
• efektivnejsi vyhledavani

Modifikovana vkladaci procedura:

• dotaz R(On,0)
• v kazdem navstivenem listu (tedy v kazdem, pro ktery neni potreba zvetsit polomer pokryti) se spocita vzdalenost k pivotu
• On je zarazen do takoveho listu, pro ktery je d(On,p) minimalni
• pokud neni navstiven zadny list, provede se klasicky one-way insert

Zakladni vlastnosti:

• modifikovany vyber podstromu pri vkladani
• modifikovana procedura split
• specialni postprocessing - slim-down algoritmus

modifikace vkladani:

• pokud ve vnitrnim uzlu existuje vice kandidatnich podstromu, vybere se ten „nejprazdnejsi“ (misto toho s nejblizsim pivotem)
• pokud neexistuje zadny, vybere se ten s nejblizsim pivotem (misto s nejmensim rozsirenim Rc)

modifikace deleni uzlu:

• pouzije algoritmus minimalni kostry na celou mnozinu P
• odstraneni nejdelsi hrany
• dve komponenty → dva nove uzly
• za pivoty se vyberou objekty s minimalni vzdalenosti k ostatnim uzlum

Zakladni vlastnosti:

• redukce fat-faktoru, efektivnejsi vyhledavani

Algoritmus:

• pro kazdy listovy uzel N
  • najdi objekt o nevzdalenejsi od pivota, najdi sousedni uzly M (v ramci podstromu ?), pro ktere o lezi v ramci Rc
  • presun o z N do M
  • prislusne zmensi Rc uzlu N
• pokud se behem celeho cyklu presune alespon jeden uzel, zopakuj
• nutno omezit pocet prubehu → zabraneni oscilacim

Zakladni vlastnosti:

• slim-down zobecneny i pro vnitrni uzly M-stromu

Algoritmus:

• na zacatku proved slim-down
• dale pokracuj zdola nahoru
• pro kazdy zaznam E = (p,Rc,...) ve vnitrnim uzlu N
  • proved R(p,Rc) - naleznou se vsechny uzly, ktere pokryvaji cely region
  • vyber takovy uzel M, pro jehoz rodicovsky pivot je blize p nez rodicovsky pivot E
  • presun E z N do M
  • pokud je mozno, zmensi Rc uzlu N

Zakladni vlastnosti:

• Rc je omezen pomoci ring-regions dalsich pivotu
• vyber dalsich pivotu p1,p2,... a dvou polomeru Rmin, Rmax
• vsechny objekty s pivotem p lezi mezi Rmin a Rmax

List:

• (o,d(o,p),PD)
• PD = {PD1,....}
• PDi = d(Pi,o)

vnitrni uzel:

• 〈p,Rc,d(p,Pp),ptr,HR〉
• HR[j].min = min({d (o, Pj) | ∀o ∈ ptr})
• HR[j].max = max({d (o, Pj) | ∀o ∈ ptr})

Zakladni vlastnosti:

• pouzitelne pouze s Lp metrikami
• koncept klicove dimenze - v n-dimenzionalnim prostoru je klicova dimenze ta, po ktere jsou objekty nejvice rozprostreny
• kazdy uzel je rozdeleny na dve „dvojcata“, podle zvolene dimenze
• mirne vylepseni pro k-NN (v PQ pouze jedno dvojce, mensi rezie na udrzbu fronty)

Vnitrni uzel:

• 〈 p, Rc , d ( p, Pp ), Dkey , ptrleft , dlmax , d rmin , ptrright 〉
  • Dkey – number of the key dimension
  • ptrleft ,ptrright – pointers to the left and right twin-nodes
  • dlmax – maximal key-dimension value of the left twin
  • drmin – minimal key-dimension value of the right twin

• Dkey je vybirana pro kazdy uzel separatne
• pro split jsou dvojcata uvazovana jako jedna mnozina

Zakladni vlastnosti:

• zobecneny M-strom pro komplexni podobnostni vyhledavani
• kombinace vice metrik

Listovy uzel(M-tree vs. M2-tree)

• 〈 o, d (o, p)〉
• 〈 o[1], d1 (o[1], p[1]), o[2], d2 (o[1], p[ 2])〉

Vnitrni uzel:

• 〈 p, Rc , d ( p, Pp ), ptr 〉
• 〈 p[1], Rc[1], d1(p[1], Pp[1]), p[2], Rc[2], d2(p[2],Pp[2]), ptr 〉

Range search:

• podminka prorezavani: ∀i, min(| di(q[i], Pp[i]) − di(p[i], Pp[i]) | − Rc [i], 0)