Repository logo
  • Log In
    New user? Click here to register.Have you forgotten your password?
University College Dublin
  • Colleges & Schools
  • Statistics
  • All of DSpace
  • Log In
    New user? Click here to register.Have you forgotten your password?
  1. Home
  2. College of Science
  3. School of Computer Science
  4. Computer Science Research Collection
  5. A computational study of external-memory BFS algorithms
 
  • Details
Options

A computational study of external-memory BFS algorithms

File(s)
FileDescriptionSizeFormat
Download ajwani_soda07.pdf250.28 KB
Author(s)
Ajwani, Deepak 
Dementiev, Roman 
Meyer, Ulrich 
Uri
http://hdl.handle.net/10197/9914
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
Keywords
  • Breadth First Search ...

  • Graph algorithms

  • Mathematics of comput...

  • Graph theory

DOI
10.1145/1109557.1109623
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
https://creativecommons.org/licenses/by-nc-nd/3.0/ie/
Owning collection
Computer Science Research Collection
Scopus© citations
45
Acquisition Date
Jan 29, 2023
View Details
Views
801
Last Week
1
Last Month
2
Acquisition Date
Jan 30, 2023
View Details
Downloads
345
Acquisition Date
Jan 30, 2023
View Details
google-scholar
University College Dublin Research Repository UCD
The Library, University College Dublin, Belfield, Dublin 4
Phone: +353 (0)1 716 7583
Fax: +353 (0)1 283 7667
Email: mailto:research.repository@ucd.ie
Guide: http://libguides.ucd.ie/rru

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Cookie settings
  • Privacy policy
  • End User Agreement