Exploring parallelisms on large-scale graph processing frameworks
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/66648 |
| _version_ | 1811682019185262592 |
|---|---|
| author | Guo, Jiachun |
| author2 | Cai Wentong |
| author_facet | Cai Wentong Guo, Jiachun |
| author_sort | Guo, Jiachun |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:50:11Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/66648 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:50:11Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | ntu-10356/666482023-03-03T20:25:14Z Exploring parallelisms on large-scale graph processing frameworks Guo, Jiachun Cai Wentong School of Computer Engineering Parallel and Distributed Computing Centre DRNTU::Engineering 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. Bachelor of Engineering (Computer Science) 2016-04-20T04:45:07Z 2016-04-20T04:45:07Z 2016 Final Year Project (FYP) http://hdl.handle.net/10356/66648 en Nanyang Technological University 47 p. application/pdf |
| spellingShingle | DRNTU::Engineering Guo, Jiachun Exploring parallelisms on large-scale graph processing frameworks |
| title | Exploring parallelisms on large-scale graph processing frameworks |
| title_full | Exploring parallelisms on large-scale graph processing frameworks |
| title_fullStr | Exploring parallelisms on large-scale graph processing frameworks |
| title_full_unstemmed | Exploring parallelisms on large-scale graph processing frameworks |
| title_short | Exploring parallelisms on large-scale graph processing frameworks |
| title_sort | exploring parallelisms on large scale graph processing frameworks |
| topic | DRNTU::Engineering |
| url | http://hdl.handle.net/10356/66648 |
| work_keys_str_mv | AT guojiachun exploringparallelismsonlargescalegraphprocessingframeworks |