1. Argument叩cia v箪beru t辿my
T辿mu o distribuovanom indexovan鱈 metrick箪ch priestorov som si vybral kv担li tomu, 転e sa jej
tieto dva semestre venujem pri p鱈san鱈 bakal叩rskej pr叩ce. T叩to t辿ma sa zaober叩 podobnostn箪m
vyh直ad叩van鱈m a jeho implement叩ciou na ve直k辿 mno転stv叩 d叩t. Ke檛e 転ijeme v dobe, kedy je
pr叩ca s inform叩ciami ve直mi d担le転it叩, tak ako sme sa nauili aj v tomto kurze, tak mi pr鱈de
tak叩to t辿ma ve直mi atrakt鱈vna, o je hlavn箪 d担vod preo som si ju vybral.
2. Distribuovan辿 indexovanie metrick箪ch priestorov
V s炭asnej dobe, kde v邸etko o poujeme, vid鱈me, 鱈tame a meriame m担転e by泥 zazname-
nan辿 digit叩lne. Preto je vyh直ad叩vanie d叩t jednou z najd担le転itej邸鱈ch schopnost鱈, ktor辿 s炭 po-
trebn辿 pre pre転itie v tomto svete. Pri takom mno転stve digit叩lnych d叩t, ak辿 je denne vypusten辿
na svet je d担le転it辿 sa v nich jednak zorientova泥, ale hlavne ich vedie泥 efekt鱈vne a r箪chlo vy-
h直ada泥.
Tu sa dost叩vame k ve直mi efekt鱈vnej vyh直ad叩vacej met坦de, podobnostn辿mu vyh直ad叩 va-
niu, ktor辿 pod直a [1] m担転eme definova泥 ako probl辿m predspracova泥 zadan炭 dom辿nu tak, aby
po転iadavky na n叩jdenie bl鱈zkych objektov boli vyhod noten辿 efekt鱈vne. Podobnostn辿 vyh直ad叩-
vanie je v箪hodnej邸ie vaka jeho mo転nosti vyh直ad叩vania priamo na d叩tach, a nie len na atrib炭-
toch d叩t, ktor辿 vyh直ad叩vame. T箪mto sa zaober叩 skupina z Fakulty informatiky Masarykovej
univerzity pod veden鱈m profesora Zezuly. Tento t箪m pracuje na projekte Multi-Feature-
Indexing Network (MUFIN), ktor辿ho snahou je vyvin炭泥 univerz叩lne technologick辿 rie邸enie
probl辿mu vyh直ad叩vania v rozsiahlych datab叩zach. Jedn箪m z v箪sledkom ich snahy je softwa-
rov箪 modul Metric Similar Search Implementation Framework (MESSIF)[2], ktor箪 bol na-
vrhnut箪 pre podporu budovania prototypu metrick辿ho indexovania na metrickom priestore,
a Metric Index (M-Index), o je inovat鱈vna indexov叩 邸trukt炭ra, ktor辿ho jadrom je v邸eobecn辿
zobrazenie z d叩tov辿ho priestoru do 鱈seln辿ho odboru.[3] Tento modul umo転uje jednoduch辿
opakovan辿 pou転itie k坦du, a zjednodu邸uje experiment叩lne ohodnocovanie, 鱈m zaruuje po-
rovn叩vanie spravodlivej邸鱈m a t箪m p叩dom s炭 v箪sledky hodnotnej邸ie.
Je v邸ak potrebn辿 vztvori泥 spo直ahlivej邸ie distribuovan辿 prostredie ako Peer-to-Peer v箪po-
tov辿 prostredie, ktor辿 pr叩ve vyu転鱈va modul MESSIF. Tak辿, kde vlastnosti m担転u by泥 zarue-
n辿 a v箪kon naladen箪 pod直a potreby. Pod直a t箪chto po転iadaviek je ide叩lnou vo直bou priestorov叩
infra邸trukt炭ra. Paraleln辿 zdroje, v箪potov箪 aj 炭lo転n箪 zdroj, mo転no vy転iada泥 na po転iadanie
pod直a potreby a ako n叩hle s炭 zadan辿, s炭 priraden辿 k aplik叩cii.
T叩to pr叩ca je zameran叩 na indexovanie metrick箪ch priestorov[4]. Metrick箪 priestor je
matematick叩 邸trukt炭ra, pomocou ktorej je mo転n辿 form叩lnym sp担sobom definova泥 pojem
vzdialenosti. Tento matematick箪 model je ve直mi v邸estrann箪 a flexibiln箪, a preto je mo転n辿 ho
efekt鱈vne vyu転i泥 v indexovacom a vyh直ad叩vacom mechanizme ak箪m je M-Index.
3. Kv担li tomuto bolo potrebn辿 sa zozn叩mi泥 s distribuovanou d叩tovou 邸trukt炭rou M-Index.
A ke檛e M-Index bol implementovan箪 v programovacom jazyku Java, bolo najvhodnej邸ie
zvoli泥 software pou転鱈vaj炭ci pr叩ve tento programovac鱈 jazyk. Konkr辿tne bola vybran叩 v箪vojo-
v叩 platforma Apache Hadoop, ktor箪 umo転uje vytv叩ra泥 aplik叩cie manipuluj炭ce s ve直k箪m
mno転stvom d叩t, ktor叩 pon炭ka napr. met坦du MapReduce, o je programovac鱈 model, pr叩ve pre
manipul叩ciu s tak箪mto mno転stvom d叩t pomocou paraleln辿ho spracovania.
Z叩kladn箪 princ鱈p MapReduce v rozdelen鱈 spracovania na mapovaciu (map) a redukova-
ciu (reduce) f叩zu, na ktor箪ch vstupe a v箪stupe s炭 usporiadan辿 dvojice (k直炭, hodnota), kto-
r箪ch typ vol鱈 program叩tor. Ten mus鱈 taktie転 邸pecifikova泥 mapovaciu a redukn炭 funkciu, kde
ka転d叩 definuje zobrazenie z jednej mno転iny dvoj鱈c (k直炭, hodnota) do druhej. MapReduce
programy s炭 inherentne paraleln辿. O distrib炭ciu 炭loh a d叩t sa star叩 syst辿m bez z叩sahu u転鱈vate-
直a.
Mojim cie直om bolo sprev叩dzkova泥 upraven炭 verziu Hadoop MapReduce, ktor叩 podpor u-
je agreg叩ciu online, o umo転uje u転鱈vate直om vidie泥 predasn辿 v箪stupy z 炭loh, zatia直 o s炭
po鱈tan辿. trukt炭ru s n叩zvom Hadoop Online Prototype (HOP)[5]. T叩to 邸trukt炭ra roz邸iruje
met坦du MapReduce o d叩vkov辿 spracovanie, zni転uje poet dokonen鱈 a taktie転 zlep邸uje vyu転i-
tie syst辿mu pre d叩vkov辿 炭lohy. Taktie転 podporuje nepretr転it辿 dotazy, o m担転e by泥 vyu転it辿 na
nap鱈sanie programov za pomoci techniky MapReduce uren箪ch na sledovanie udalost鱈
Najd担le転itej邸ie kroky pre dosiahnutie vy邸邸ie uveden辿ho cie直u s炭 rozobrat辿 v nasleduj 炭-
cich kapitol叩ch: v prvej kapitole je bli転邸ie pop鱈san箪 M-Index a jednotliv辿 asti sekvenn辿ho
postupu, ktor辿 boli pou転鱈van辿 pri tvorbe d叩tovej 邸trukt炭ry doteraz. V druhej kapitole je po-
drobnej邸ie vysvetlen叩 funkcionalita Hadoop MapReduce a vz泥ah s Hadoop Online Protype.
V al邸ej kapitole je okomentovan箪 hlavn箪 v箪stup pr叩ce: zdrojov箪 k坦d z jednotliv箪ch tried
v jazyku Java, nastavenie a sp担sob pr叩ce s v箪sledn箪m programom. V箪sledky testovania na
re叩lnych d叩tach s炭 obsiahnut辿 v posledn箪ch astiach textu.
[1] ZEZULA P., AMATO G., DOHNAL V. and BATKO M. Similarity Search: The Metric
Space Approach. vol. 32 of Advances in Database Systems. Springer, 2006. Dostupn辿 na:
<http://www.nmis.isti.cnr.it/amato/similarity-search-book/>
[2] BATKO M., NOVAK D. and ZEZULA P. MESSIF: Metric similiarity search imple-
mentation framework, in First International DELOS Conference. Pisa, Italy, Revised
4. Selected Papers. vol. 4877 of Lecture Notes in Computer Science. pp. 1-10. Springer,
2007.Dostupn辿 na:
<http://www.fi.muni.cz/~xnovak8/papers/batkonovakzezula07messif.pdf>
[3] NOVAK D., BATKO M. and ZEZULA P. Metric Index: An efficient and scalable solu-
tion for precise and approximate similiarity search, Information Systems. vol. 36. pp.
721-733. June 2011. Dostupn辿 na:
<http://sisap.org/2009/presentations/mindex.pdf>
[4] BATKO M., DOHNAL V. and ZEZULA P. "M-Grid: similarity searching in
grid." Proceedings of the international workshop on Information retrieval in peer-to-peer
networks. ACM, 2006. Dostupn辿 na:
<http://www.cs.cas.cz/semweb/download.php?file=cikm2006wo rkshop&type=pdf>
[5] Condie, T., Conway, N., Alvaro, P., Hellerstein, J. M., Elmeleegy, K., & Sears, R.,
"MapReduce online." Proceedings of the 7th USENIX conference on Networked systems
design and implementation. 2010. Dostupn辿 na:
http://db.cs.berkeley.edu/papers/nsdi10- hop.pdf
Zdroje s炭 relevantn辿, preto転e:
1. Autori s炭 d担veryhodn箪
2. Odbornos泥 textov
3. Vysvet直uj炭 pojmy potrebn辿 k pr叩ci
4. Sl炭転ia ako v箪ubov辿 materi叩ly
![Distribuovan辿 indexovanie metrick箪ch priestorov
V s炭asnej dobe, kde v邸etko o poujeme, vid鱈me, 鱈tame a meriame m担転e by泥 zazname-
nan辿 digit叩lne. Preto je vyh直ad叩vanie d叩t jednou z najd担le転itej邸鱈ch schopnost鱈, ktor辿 s炭 po-
trebn辿 pre pre転itie v tomto svete. Pri takom mno転stve digit叩lnych d叩t, ak辿 je denne vypusten辿
na svet je d担le転it辿 sa v nich jednak zorientova泥, ale hlavne ich vedie泥 efekt鱈vne a r箪chlo vy-
h直ada泥.
Tu sa dost叩vame k ve直mi efekt鱈vnej vyh直ad叩vacej met坦de, podobnostn辿mu vyh直ad叩 va-
niu, ktor辿 pod直a [1] m担転eme definova泥 ako probl辿m predspracova泥 zadan炭 dom辿nu tak, aby
po転iadavky na n叩jdenie bl鱈zkych objektov boli vyhod noten辿 efekt鱈vne. Podobnostn辿 vyh直ad叩-
vanie je v箪hodnej邸ie vaka jeho mo転nosti vyh直ad叩vania priamo na d叩tach, a nie len na atrib炭-
toch d叩t, ktor辿 vyh直ad叩vame. T箪mto sa zaober叩 skupina z Fakulty informatiky Masarykovej
univerzity pod veden鱈m profesora Zezuly. Tento t箪m pracuje na projekte Multi-Feature-
Indexing Network (MUFIN), ktor辿ho snahou je vyvin炭泥 univerz叩lne technologick辿 rie邸enie
probl辿mu vyh直ad叩vania v rozsiahlych datab叩zach. Jedn箪m z v箪sledkom ich snahy je softwa-
rov箪 modul Metric Similar Search Implementation Framework (MESSIF)[2], ktor箪 bol na-
vrhnut箪 pre podporu budovania prototypu metrick辿ho indexovania na metrickom priestore,
a Metric Index (M-Index), o je inovat鱈vna indexov叩 邸trukt炭ra, ktor辿ho jadrom je v邸eobecn辿
zobrazenie z d叩tov辿ho priestoru do 鱈seln辿ho odboru.[3] Tento modul umo転uje jednoduch辿
opakovan辿 pou転itie k坦du, a zjednodu邸uje experiment叩lne ohodnocovanie, 鱈m zaruuje po-
rovn叩vanie spravodlivej邸鱈m a t箪m p叩dom s炭 v箪sledky hodnotnej邸ie.
Je v邸ak potrebn辿 vztvori泥 spo直ahlivej邸ie distribuovan辿 prostredie ako Peer-to-Peer v箪po-
tov辿 prostredie, ktor辿 pr叩ve vyu転鱈va modul MESSIF. Tak辿, kde vlastnosti m担転u by泥 zarue-
n辿 a v箪kon naladen箪 pod直a potreby. Pod直a t箪chto po転iadaviek je ide叩lnou vo直bou priestorov叩
infra邸trukt炭ra. Paraleln辿 zdroje, v箪potov箪 aj 炭lo転n箪 zdroj, mo転no vy転iada泥 na po転iadanie
pod直a potreby a ako n叩hle s炭 zadan辿, s炭 priraden辿 k aplik叩cii.
T叩to pr叩ca je zameran叩 na indexovanie metrick箪ch priestorov[4]. Metrick箪 priestor je
matematick叩 邸trukt炭ra, pomocou ktorej je mo転n辿 form叩lnym sp担sobom definova泥 pojem
vzdialenosti. Tento matematick箪 model je ve直mi v邸estrann箪 a flexibiln箪, a preto je mo転n辿 ho
efekt鱈vne vyu転i泥 v indexovacom a vyh直ad叩vacom mechanizme ak箪m je M-Index.](https://image.slidesharecdn.com/zaverecnauloha-121228130315-phpapp01/85/Zaverecna-uloha-KPI-2-320.jpg)
![Kv担li tomuto bolo potrebn辿 sa zozn叩mi泥 s distribuovanou d叩tovou 邸trukt炭rou M-Index.
A ke檛e M-Index bol implementovan箪 v programovacom jazyku Java, bolo najvhodnej邸ie
zvoli泥 software pou転鱈vaj炭ci pr叩ve tento programovac鱈 jazyk. Konkr辿tne bola vybran叩 v箪vojo-
v叩 platforma Apache Hadoop, ktor箪 umo転uje vytv叩ra泥 aplik叩cie manipuluj炭ce s ve直k箪m
mno転stvom d叩t, ktor叩 pon炭ka napr. met坦du MapReduce, o je programovac鱈 model, pr叩ve pre
manipul叩ciu s tak箪mto mno転stvom d叩t pomocou paraleln辿ho spracovania.
Z叩kladn箪 princ鱈p MapReduce v rozdelen鱈 spracovania na mapovaciu (map) a redukova-
ciu (reduce) f叩zu, na ktor箪ch vstupe a v箪stupe s炭 usporiadan辿 dvojice (k直炭, hodnota), kto-
r箪ch typ vol鱈 program叩tor. Ten mus鱈 taktie転 邸pecifikova泥 mapovaciu a redukn炭 funkciu, kde
ka転d叩 definuje zobrazenie z jednej mno転iny dvoj鱈c (k直炭, hodnota) do druhej. MapReduce
programy s炭 inherentne paraleln辿. O distrib炭ciu 炭loh a d叩t sa star叩 syst辿m bez z叩sahu u転鱈vate-
直a.
Mojim cie直om bolo sprev叩dzkova泥 upraven炭 verziu Hadoop MapReduce, ktor叩 podpor u-
je agreg叩ciu online, o umo転uje u転鱈vate直om vidie泥 predasn辿 v箪stupy z 炭loh, zatia直 o s炭
po鱈tan辿. trukt炭ru s n叩zvom Hadoop Online Prototype (HOP)[5]. T叩to 邸trukt炭ra roz邸iruje
met坦du MapReduce o d叩vkov辿 spracovanie, zni転uje poet dokonen鱈 a taktie転 zlep邸uje vyu転i-
tie syst辿mu pre d叩vkov辿 炭lohy. Taktie転 podporuje nepretr転it辿 dotazy, o m担転e by泥 vyu転it辿 na
nap鱈sanie programov za pomoci techniky MapReduce uren箪ch na sledovanie udalost鱈
Najd担le転itej邸ie kroky pre dosiahnutie vy邸邸ie uveden辿ho cie直u s炭 rozobrat辿 v nasleduj 炭-
cich kapitol叩ch: v prvej kapitole je bli転邸ie pop鱈san箪 M-Index a jednotliv辿 asti sekvenn辿ho
postupu, ktor辿 boli pou転鱈van辿 pri tvorbe d叩tovej 邸trukt炭ry doteraz. V druhej kapitole je po-
drobnej邸ie vysvetlen叩 funkcionalita Hadoop MapReduce a vz泥ah s Hadoop Online Protype.
V al邸ej kapitole je okomentovan箪 hlavn箪 v箪stup pr叩ce: zdrojov箪 k坦d z jednotliv箪ch tried
v jazyku Java, nastavenie a sp担sob pr叩ce s v箪sledn箪m programom. V箪sledky testovania na
re叩lnych d叩tach s炭 obsiahnut辿 v posledn箪ch astiach textu.
[1] ZEZULA P., AMATO G., DOHNAL V. and BATKO M. Similarity Search: The Metric
Space Approach. vol. 32 of Advances in Database Systems. Springer, 2006. Dostupn辿 na:
<http://www.nmis.isti.cnr.it/amato/similarity-search-book/>
[2] BATKO M., NOVAK D. and ZEZULA P. MESSIF: Metric similiarity search imple-
mentation framework, in First International DELOS Conference. Pisa, Italy, Revised](https://image.slidesharecdn.com/zaverecnauloha-121228130315-phpapp01/85/Zaverecna-uloha-KPI-3-320.jpg)
![Selected Papers. vol. 4877 of Lecture Notes in Computer Science. pp. 1-10. Springer,
2007.Dostupn辿 na:
<http://www.fi.muni.cz/~xnovak8/papers/batkonovakzezula07messif.pdf>
[3] NOVAK D., BATKO M. and ZEZULA P. Metric Index: An efficient and scalable solu-
tion for precise and approximate similiarity search, Information Systems. vol. 36. pp.
721-733. June 2011. Dostupn辿 na:
<http://sisap.org/2009/presentations/mindex.pdf>
[4] BATKO M., DOHNAL V. and ZEZULA P. "M-Grid: similarity searching in
grid." Proceedings of the international workshop on Information retrieval in peer-to-peer
networks. ACM, 2006. Dostupn辿 na:
<http://www.cs.cas.cz/semweb/download.php?file=cikm2006wo rkshop&type=pdf>
[5] Condie, T., Conway, N., Alvaro, P., Hellerstein, J. M., Elmeleegy, K., & Sears, R.,
"MapReduce online." Proceedings of the 7th USENIX conference on Networked systems
design and implementation. 2010. Dostupn辿 na:
http://db.cs.berkeley.edu/papers/nsdi10- hop.pdf
Zdroje s炭 relevantn辿, preto転e:
1. Autori s炭 d担veryhodn箪
2. Odbornos泥 textov
3. Vysvet直uj炭 pojmy potrebn辿 k pr叩ci
4. Sl炭転ia ako v箪ubov辿 materi叩ly](https://image.slidesharecdn.com/zaverecnauloha-121228130315-phpapp01/85/Zaverecna-uloha-KPI-4-320.jpg)
