Iterative Computation of Connected Graph Components with MapReduce
Abstract
The use of the MapReduce framework for iterative graph algorithms is challenging. To achieve high performance it is critical to limit the amount of intermediate results as well as the number of necessary iterations. We address these issues for the important problem of finding connected components in large graphs. We analyze an existing MapReduce algorithm, CC-MR, and present techniques to improve its performance including a memory-based connection of subgraphs in the map phase. Our evaluation with several large graph datasets shows that the improvements can substantially reduce the amount of generated data by up to a factor of 8.8 and runtime by up to factor of 3.5.
- Citation
- BibTeX
Kolb, L., Sehili, Z. & Rahm, E.,
(2014).
Iterative Computation of Connected Graph Components with MapReduce.
Datenbank-Spektrum: Vol. 14, No. 2.
Springer.
(S. 107-117).
DOI: 10.1007/s13222-014-0154-1
@article{mci/Kolb2014,
author = {Kolb, Lars AND Sehili, Ziad AND Rahm, Erhard},
title = {Iterative Computation of Connected Graph Components with MapReduce},
journal = {Datenbank-Spektrum},
volume = {14},
number = {2},
year = {2014},
,
pages = { 107-117 } ,
doi = { 10.1007/s13222-014-0154-1 }
}
author = {Kolb, Lars AND Sehili, Ziad AND Rahm, Erhard},
title = {Iterative Computation of Connected Graph Components with MapReduce},
journal = {Datenbank-Spektrum},
volume = {14},
number = {2},
year = {2014},
,
pages = { 107-117 } ,
doi = { 10.1007/s13222-014-0154-1 }
}
Sollte hier kein Volltext (PDF) verlinkt sein, dann kann es sein, dass dieser aus verschiedenen Gruenden (z.B. Lizenzen oder Copyright) nur in einer anderen Digital Library verfuegbar ist. Versuchen Sie in diesem Fall einen Zugriff ueber die verlinkte DOI: 10.1007/s13222-014-0154-1
Haben Sie fehlerhafte Angaben entdeckt? Sagen Sie uns Bescheid: Send Feedback
More Info
ISSN: 1610-1995
xmlui.MetaDataDisplay.field.date: 2014
Content Type: Text/Journal Article