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

Author(s)
Ajwani, Deepak  
Dementiev, Roman  
Meyer, Ulrich  
Uri
http://hdl.handle.net/10197/9914
Date Issued
2006-01-26
Date Available
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.
Other Sponsorship
DFG
Type of Material
Conference Publication
Publisher
ACM
Copyright (Published Version)
2006 ACM
Subjects

Breadth First Search ...

Graph algorithms

Mathematics of comput...

Graph theory

DOI
10.1145/1109557.1109623
Language
English
Status of Item
Not peer reviewed
Journal
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
This item is made available under a Creative Commons License
https://creativecommons.org/licenses/by-nc-nd/3.0/ie/
File(s)
No Thumbnail Available
Name

ajwani_soda07.pdf

Size

250.28 KB

Format

Adobe PDF

Checksum (MD5)

d5ac02491c80b83765cdd52ebf41ed96

Owning collection
Computer Science Research Collection

Item descriptive metadata is released under a CC-0 (public domain) license: https://creativecommons.org/public-domain/cc0/.
All other content is subject to copyright.

For all queries please contact research.repository@ucd.ie.

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

  • Cookie settings
  • Privacy policy
  • End User Agreement