Improved external memory BFS implementations

Files in This Item:
File Description SizeFormat 
ajwani_alenex07.pdf761.26 kBAdobe PDFDownload
Title: Improved external memory BFS implementations
Authors: Ajwani, Deepak
Meyer, Ulrich
Osipov, Vitaly
Permanent link:
Date: 6-Jan-2007
Online since: 2019-05-20T07:47:04Z
Abstract: Breadth first search (BPS) traversal on massive graphs in external memory was considered non-viable until recently, because of the large number of I/Os it incurs. Ajwani et al. [3] showed that the randomized variant of the o(n) I/O algorithm of Mehlhorn and Meyer [24] (MM.BFS) can compute the BPS level decomposition for large graphs (around a billion edges) in a few hours for small diameter graphs and a few days for large diameter graphs. We improve upon their implementation of this algorithm by reducing the overhead associated with each BPS level, thereby improving the results for large diameter graphs which are more difficult for BPS traversal in external memory. Also, we present the implementation of the deterministic variant of MM.BFS and show that in most cases, it outperforms the randomized variant. The running time for BPS traversal is further improved with a heuristic that preserves the worst case guarantees of MM_BFS, Together, they reduce the time for BFS on large diameter graphs from days shown in [3] to hours. In particular, on line graphs with random layout on disks, our implementation of the deterministic variant of MM_BFS with the proposed heuristic is more than 75 times faster than the previous best result for the randomized variant of MM.BFS in [3].
Type of material: Conference Publication
Publisher: Society for Industrial and Applied Mathematics Philadelphia
Copyright (published version): 2007 Society for Industrial and Applied Mathematics Philadelphia, PA, USA
Keywords: Breadth first search (BPS)Graph algorithmsBPS traversalBFS algorithms
Language: en
Status of Item: Not peer reviewed
Is part of: Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Conference Details: ALEXNEX07/ ANACO04: Workshop on Algorithm Engineering & Experiments, 6 January 2007, Astor Crowne Plaza, New Orleans, Louisiana
ISBN: 0898716284
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.