Experimental implementation on external memory breadth-first search algorithm

• Main Author: Poh, Eric Jian Wen.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2011
• Subjects: DRNTU::Engineering::Computer science and engineering::Data::Data structures; DRNTU::Engineering::Computer science and engineering::Software::Software engineering
• Online Access: http://hdl.handle.net/10356/43936
• Institution: Nanyang Technological University

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.