Please use this identifier to cite or link to this item:
Title: Exploring parallelisms on large-scale graph processing frameworks
Authors: Guo, Jiachun
Keywords: DRNTU::Engineering
Issue Date: 2016
Abstract: Large-scale graph-structured computation is becoming increasingly important for various data analysis applications, and has driven the development of various distributed graph processing frameworks. However, existing framework abstractions do not directly support efficient implementation for complex algorithms including graph traversal algorithms. This project leverages the properties of small-world scale-free graphs, which apply to many real-world datasets, and implements an efficient Hybrid BFS algorithm and a Concurrent BFS algorithm on PowerGraph. Hybrid BFS algorithm combines a conventional top-down approach and a novel bottom-up approach to improve the overall performance, while concurrent BFS algorithm runs multiple BFSs on the same graph at the same time and shares explorations across them. Extensive experiments are conducted on two real-world graph datasets to evaluate the performance of Hybrid BFS and concurrent BFS algorithms. The results reveal that Hybrid BFS outperforms traditional top-down approach, and concurrent BFS algorithm has higher resource utilization, efficiency and scalability with respect to the number of concurrent BFSs.
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
FYP Amended Report1.51 MBAdobe PDFView/Open

Page view(s)

Updated on Nov 28, 2020

Google ScholarTM


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