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

Files in This Item:
File Description SizeFormat 
ajwani_arcs12.pdf364.92 kBAdobe PDFDownload
Title: I/O-efficient approximation of graph diameters by parallel cluster growing - A first experimental study
Authors: Ajwani, Deepak
Beckmann, Andreas
Meyer, Ulrich
Veith, David
Permanent link: http://hdl.handle.net/10197/9899
Date: 21-Jun-2012
Online since: 2019-04-11T07:38:44Z
Abstract: A 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 (2008) 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 (Meyer, 2008) suggests.
Type of material: Conference Publication
Publisher: IEEE
Start page: 1
End page: 7
Copyright (published version): 2012 IEEE
Keywords: Approximation methodsApproximation algorithmsUpper boundRandom access memoryHeuristic algorithmsMemory managementSorting
Other versions: https://ieeexplore.ieee.org/document/6222204
Language: en
Status of Item: Peer reviewed
Conference Details: The 2012 Architecture of Computing Systems (ARCS), Munchen, Germany, 28 February - 2 March 2012
ISBN: 978-1-4673-1913-3
Appears in Collections:Computer Science Research Collection

Show full item record

Google ScholarTM



This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.