Please use this identifier to cite or link to this item:
Title: Experimental implementation on external memory breadth-first search algorithm
Authors: Poh, Eric Jian Wen.
Keywords: DRNTU::Engineering::Computer science and engineering::Data::Data structures
DRNTU::Engineering::Computer science and engineering::Software::Software engineering
Issue Date: 2011
Abstract: Modern day’s databases contain over hundred gigabytes to petabytes of information. For efficient and fast processing of such large amount of data, it will be desirable if all information can be stored in a computer system’s main memory for processing. However in reality, that is not the case as slower secondary storage mediums are normally preferred to contain such large data sets. Therefore, in the field of data management, there is an important need for efficient data processing algorithms using external memory to process large data sets. Breadth-First Search (BFS) traversal is one of the most basic and essential graph processing operations. To perform BFS on massive undirected graph is considered to be I/O efficiency problem. Traditional BFS algorithm will not be scalable to perform BFS operation on such large graph due to the number of I/O operations involved. The solution to this problem will be to implement external memory BFS algorithm for efficient computations. In this project, the Munagala and Ranade algorithm is being studied and implemented to perform BFS in external memory model. The main objective is to implement an I/O efficient external memory algorithm to perform Breadth-First search on large graph in the lowest possible time.
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SCSE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
  Restricted Access
2.32 MBAdobe PDFView/Open

Page view(s) 10

Updated on Feb 27, 2021


Updated on Feb 27, 2021

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.