Options
A computational study of external-memory BFS algorithms
File(s)
File | Description | Size | Format | |
---|---|---|---|---|
ajwani_soda07.pdf | 250.28 KB |
Author(s)
Date Issued
26 January 2006
Date Available
11T10:30:19Z April 2019
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.
Other Sponsorship
DFG
Type of Material
Conference Publication
Publisher
ACM
Copyright (Published Version)
2006 ACM
Language
English
Status of Item
Not peer reviewed
Part of
SODA '06 Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
Description
The Seventeenth Annual ACM-SIAM Symposium on Discrete Algorith (SODA '06), Miami, Florida, 22-26 January 2006
ISBN
978-0-89871-605-4
This item is made available under a Creative Commons License
Owning collection
Scopus© citations
45
Acquisition Date
Jan 29, 2023
Jan 29, 2023
Views
801
Last Week
1
1
Last Month
2
2
Acquisition Date
Jan 30, 2023
Jan 30, 2023
Downloads
345
Acquisition Date
Jan 30, 2023
Jan 30, 2023