Iterative Computation of Connected Graph Components with MapReduce

dc.contributor.author	Kolb, Lars
dc.contributor.author	Sehili, Ziad
dc.contributor.author	Rahm, Erhard
dc.date.accessioned	2018-01-10T13:19:39Z
dc.date.available	2018-01-10T13:19:39Z
dc.date.issued	2014
dc.description.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.
dc.identifier.pissn	1610-1995
dc.identifier.uri	https://dl.gi.de/handle/20.500.12116/11710
dc.publisher	Springer
dc.relation.ispartof	Datenbank-Spektrum: Vol. 14, No. 2
dc.relation.ispartofseries	Datenbank-Spektrum
dc.subject	Connected graph components
dc.subject	Hadoop
dc.subject	MapReduce
dc.subject	Transitive closure
dc.title	Iterative Computation of Connected Graph Components with MapReduce
dc.type	Text/Journal Article
gi.citation.endPage	117
gi.citation.startPage	107

Sammlungen