Logo des Repositoriums
 

I/O-efficient approximation of graph diameters by parallel cluster growing — a first experimental study

Kurzanzeige
dc.contributor.authorAjwani, Deepak
dc.contributor.authorBeckmann, Andreas
dc.contributor.authorMeyer, Ulrich
dc.contributor.authorVeith, David
dc.date.accessioned2017-12-06T09:10:05Z
dc.date.available2017-12-06T09:10:05Z
dc.date.issued2012
dc.description.abstractA fundamental step in the analysis of a massive graph is to compute its diameter. In the RAM model, the diameter of a connected undirected unweighted graph can be efficiently 2-approximated using a Breadth-First Search (BFS) traversal from an arbitrary node. However, if the graph is stored on disk, even an external memory BFS traversal is prohibitive, owing to the large number of I/Os it incurs. Meyer [Mey08] proposed a parametrized algorithm to compute an approximation of graph diameter with fewer I/Os than that required for exact BFS traversal of the graph. The approach is based on growing clusters around randomly chosen vertices `in parallel' until their fringes meet. We present an implementation of this algorithm and compare it with some simple heuristics and external-memory BFS in order to determine the trade-off between the approximation ratio and running-time achievable in practice. Our experiments show that with carefully chosen parameters, the new approach is indeed capable to produce surprisingly good diameter approximations in shorter time. We also confirm experimentally, that there are graph-classes where the parametrized approach runs into bad approximation ratios just as the theoretical analysis in [Mey08] suggests.en
dc.identifier.doi10.1007/BF03342028
dc.identifier.pissn0177-0454
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/8610
dc.language.isoen
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofPARS: Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware: Vol. 29, No. 1
dc.relation.ispartofseriesPARS: Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware
dc.subjectExternal Memory
dc.subjectMaster Node
dc.subjectGraph Class
dc.subjectInternal Memory
dc.subjectReal World Graph
dc.titleI/O-efficient approximation of graph diameters by parallel cluster growing — a first experimental studyen
dc.typeText/Journal Article
gi.citation.endPage86
gi.citation.startPage75

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild
Name:
40731_2014_Article_BF03342028.pdf
Größe:
168.28 KB
Format:
Adobe Portable Document Format
Herunterladen

Sammlungen

PARS-Mitteilungen 2012