is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7416

Titill: 
  • Titill er á ensku Distributed cluster pruning in Hadoop
  • Cluster pruning dreifð með Hadoop
Námsstig: 
  • Meistara
Útdráttur: 
  • Útdráttur er á ensku

    Clustering is a technique used to partition data into groups or clusters based on content. Clustering techniques are sometimes used to create an index from clusters to accelerate query processing. Recently the cluster pruning method was proposed which is a randomized clustering algorithm that produces clusters and an index both efficiently and effectively. The cluster pruning method runs in a single process and is executed on one machine. The time it takes to cluster a data collection on a single computer therefore becomes unacceptable due to increasing size of data collections.
    Hadoop is a framework that supports data-intensive distributed applications and is used to process data on thousands of computers. In this report we adapt the cluster pruning method to the Hadoop framework. Two scalable distributed clustering methods are proposed: the Single Clustered File method and the Multiple Clustered Files method. Both methods were executed on one to eight machines in Hadoop and were compared to an implementation of the cluster pruning method which does not execute in Hadoop. The results show that using the Single Clustered File method with eight machines took only 15% of the time it took the original cluster pruning method to cluster a data collection while maintaining the cluster quality. The original method, however, gave slightly better search time when compared to the execution of the Single Clustered File method in Hadoop with eight nodes. The results indicate that the best performance is achieved by combining the Single Clustered File method for clustering and the original method, outside of Hadoop, for searching. In the experiments, the input to both methods was a text file with multiple descriptors, so even better performance can be reached by using binary files.,

  • Þyrping gagna (e. clustering) er aðferð þar sem gögn er hafa svipaða eiginleika eru sett saman í hóp. Til eru nokkrar aðferðir við þyrpingu gagna, sumar þessarra aðferða búa einnig til vísi sem er notaður til þess að hraða fyrirspurnum. Nýleg aðferð sem heitir „cluster pruning” velur af handahófi punkta til þess að þyrpa eftir og býr jafnframt til vísi yfir þyrpingarnar. Þessi aðferð hefur skilað góðum og skilvirkum niðurstöðum bæði fyrir þyrpingu og fyrirspurnir. Cluster pruning aðferðin er keyrð á einni vél. Sá tími sem tekur eina vél að skipta gagnasafni upp í hópa er að lengjast þar sem gagnasöfnin eru sífellt að stækka. Því er þörf á að minnka vinnslutímann svo að hann sé innan ásættanlegra marka.
    Hadoop er kerfi sem styður hugbúnað er vinnur með mikið magn af gögnum. Hadoop kerfið dreifir vinnslunni á gögnunum yfir margar vélar og flýtir þar með keyrslu hugbúnaðarins. Í þessu verkefni var cluster pruning aðferðin aðlöguð að Hadoop kerfinu. Lagðar voru fram tvær aðferðir sem byggja á cluster pruning aðferðinni; Single Clustered File aðferð og Multiple Clustered Files aðferð. Báðar aðferðirnar voru keyrðar á einni til átta tölvum í Hadoop kerfinu og þær bornar saman við upprunalega afbrigðið af cluster pruning sem er ekki keyrt í Hadoop kerfinu. Niðurstöður sýndu að þegar Single Clustered File aðferðin var keyrð á átta tölvum þá tók það aðeins 15% af tímanum sem það tók upprunalega cluster pruning aðferðina að þyrpa gögnin og jafnframt náði hún að viðhalda sömu gæðum. Upprunalega cluster pruning aðferðin gaf örlítið betri leitartíma þegar hún er borin saman við keyrslu á Single Clustered File aðferðinni í Hadoop þegar notast var við átta tölvur. Rannsóknin sýnir að með því að nota saman Single Clustered File method við þyrpingu gagna og upprunalega afbrigðið af cluster pruning við leit, án Hadoop, þá nást bestu afköstin. Við prófanir voru báðar aðferðirnar að vinna með textaskrár en hægt væri að ná betri tíma við þyrpingu gagna með því að nota tvíundaskrár (e. binary files).

Athugasemdir: 
  • Tölvunarfræði, Thesis
Samþykkt: 
  • 25.1.2011
URI: 
  • http://hdl.handle.net/1946/7416


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
MSc_AndriMarBjorgvinsson.pdf243.25 kBOpinnHeildartextiPDFSkoða/Opna