Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Distributed balanced edge-cut partitioning of large graphs having weighted vertices
KTH, School of Information and Communication Technology (ICT).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Large scale graphs are sometimes too big to store and process on a single machine. Instead, these graphs have to be divided into smaller parts and distributed over several machines, while minimizing the dependency between the different parts. This is known as the graph partitioning problem, which has been shown to be NP-complete. The problem is well studied, however most solutions are either not suitable for a distributed environment or unable to do balanced partitioning of graphs having weighted vertices. This thesis presents an extension to the distributed balanced graph partitioning algorithm JA-BE-JA, that solves the balanced partitioning problem for graph having weighted vertices. The extension, called wJA-BE-JA, is implemented in both the Spark framework and in Scala. The two main contributions of this report are the algorithm and a comprehensive evaluation of its performance, including a comparison with the recognized METIS graph partitioner. The evaluation shows that a random sampling policy in combination with the simulated annealing technique gives good results. It further shows that the algorithm is competitive to METIS, as the extension outperforms METIS in 17 of 20 tests.

Place, publisher, year, edition, pages
2015.
Series
TRITA-ICT-EX, 2015:46
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-175145OAI: oai:DiVA.org:kth-175145DiVA: diva2:860026
Examiners
Available from: 2015-10-09 Created: 2015-10-09 Last updated: 2017-06-14Bibliographically approved

Open Access in DiVA

fulltext(2999 kB)5 downloads
File information
File name FULLTEXT01.pdfFile size 2999 kBChecksum SHA-512
444e9797ad6972d2e6ca465f77c6a5c339d06c7a3f53f3c9955c82de1f377dac0ddff97820b3db978986592bd922a36cbfb639ac4c9a44da3ba3b74c98347ff5
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 5 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

urn-nbn

Altmetric score

urn-nbn
Total: 117 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf