Change search
ReferencesLink to record
Permanent link

Direct link
Using Map-Reduce for Large Scale Analysis of Graph-Based Data
KTH, School of Information and Communication Technology (ICT).
2011 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

As social networks have gained in popularity, maintaining and processing the social network graph information using graph algorithms has become an essential source for discovering potential features of the graph. The escalating size of the social networks has made it impossible to process the huge graphs on a single ma chine in a “real-time” level of execution. This thesis is looking into representing and distributing graph-based algorithms using Map-Reduce model.

Graph-based algorithms are discussed in the beginning. Then, several distributed graph computing infrastructures are reviewed, followed by Map-Reduce introduction and some graph computation toolkits based on Map-Reduce model. By reviewing the background and related work, graph-based algorithms are categorized, and adaptation of graph-based algorithms to Map-Reduce model is discussed. Two particular algorithms, MCL and DBSCAN are chosen to be designed using Map- Reduce model, and implemented using Hadoop. New matrix multiplication method is proposed while designing MCL. The DBSCAN is reformulated into connectivity problem using filter method, and Kingdom Expansion Game is proposed to do fast expansion. Scalability and performance of these new designs are evaluated. Conclusion is made according to the literature study, practical design experience and evaluation data. Some suggestions of graph-based algorithms design using Map-Reduce model are also given in the end.

Place, publisher, year, edition, pages
2011. , 74 p.
Trita-ICT-EX, 2011:218
National Category
Engineering and Technology
URN: urn:nbn:se:kth:diva-102822OAI: diva2:556816
Educational program
Master of Science - Software Engineering of Distributed Systems
Available from: 2012-09-26 Created: 2012-09-26 Last updated: 2012-09-26Bibliographically approved

Open Access in DiVA

fulltext(1249 kB)1848 downloads
File information
File name FULLTEXT01.pdfFile size 1249 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 1848 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 336 hits
ReferencesLink to record
Permanent link

Direct link