A computational study of external-memory BFS algorithms
|Title:||A computational study of external-memory BFS algorithms||Authors:||Ajwani, Deepak
|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 algorithms; Mathematics of computing; Graph 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
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.