A computational study of external-memory BFS algorithms

Files in This Item:
File Description SizeFormat 
ajwani_soda07.pdf250.28 kBAdobe PDFDownload
Title: A computational study of external-memory BFS algorithms
Authors: Ajwani, Deepak
Dementiev, Roman
Meyer, Ulrich
Permanent link: http://hdl.handle.net/10197/9914
Date: 26-Jan-2006
Online since: 2019-04-11T10:30:19Z
Abstract: Breadth First Search (BFS) traversal is an archetype for many important graph problems. However, computing a BFS level decomposition for massive graphs was considered nonviable so far, because of the large number of I/Os it incurs. This paper presents the first experimental evaluation of recent external-memory BFS algorithms for general graphs. With our STXXL based implementations exploiting pipelining and disk-parallelism, we were able to compute the BFS level decomposition of a web-crawl based graph of around 130 million nodes and 1.4 billion edges in less than 4 hours using single disk and 2.3 hours using 4 disks. We demonstrate that some rather simple external-memory algorithms perform significantly better (minutes as compared to hours) than internal-memory BFS, even if more than half of the input resides internally.
Type of material: Conference Publication
Publisher: ACM
Copyright (published version): 2006 ACM
Keywords: Breadth First Search (BFS)Graph algorithmsMathematics of computingGraph theory
DOI: 10.1145/1109557.1109623
Language: en
Status of Item: Not peer reviewed
Is part of: SODA '06 Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
Conference Details: The Seventeenth Annual ACM-SIAM Symposium on Discrete Algorith (SODA '06), Miami, Florida, 22-26 January 2006
ISBN: 978-0-89871-605-4
Appears in Collections:Computer Science Research Collection

Show full item record

Citations 10

Last Week
Last month
checked on May 19, 2019

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.