GI LogoGI Logo
  • Login
Digital Library
    • All of DSpace

      • Communities & Collections
      • Titles
      • Authors
      • By Issue Date
      • Subjects
    • This Collection

      • Titles
      • Authors
      • By Issue Date
      • Subjects
Digital Library Gesellschaft für Informatik e.V.
GI-DL
    • English
    • Deutsch
  • English 
    • English
    • Deutsch
View Item 
  •   DSpace Home
  • Fachbereiche
  • Datenbanken und Informationssysteme (DBIS)
  • Datenbank Spektrum
  • Datenbank Spektrum 14(2) - Juli 2014
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
  •   DSpace Home
  • Fachbereiche
  • Datenbanken und Informationssysteme (DBIS)
  • Datenbank Spektrum
  • Datenbank Spektrum 14(2) - Juli 2014
  • View Item

Iterative Computation of Connected Graph Components with MapReduce

Author:
Kolb, Lars [DBLP] ;
Sehili, Ziad [DBLP] ;
Rahm, Erhard [DBLP]
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 }
}

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

DOI: 10.1007/s13222-014-0154-1
ISSN: 1610-1995
xmlui.MetaDataDisplay.field.date: 2014
Content Type: Text/Journal Article

Keywords

  • Connected graph components
  • Hadoop
  • MapReduce
  • Transitive closure
Collections
  • Datenbank Spektrum 14(2) - Juli 2014 [10]

Show full item record


About uns | FAQ | Help | Imprint | Datenschutz

Gesellschaft für Informatik e.V. (GI), Kontakt: Geschäftsstelle der GI
Diese Digital Library basiert auf DSpace.

 

 


About uns | FAQ | Help | Imprint | Datenschutz

Gesellschaft für Informatik e.V. (GI), Kontakt: Geschäftsstelle der GI
Diese Digital Library basiert auf DSpace.