An efficient iterative graph data processing framework based on bulk synchronous parallel model. (22nd January 2018)

• Record Type: Journal Article
• Authors: Liu, Chao; Zeng, Deze; Yao, Hong; Yan, Xuesong; Yu, Linchen; Fu, Zhangjie
• Other Names: Jin Hai guestEditor.; Shen Xipeng guestEditor.; Lovas Robert guestEditor.; Liao Xiaofei guestEditor.; Skjellum Anthony guestEditor.; Bangalore Purushotham V. guestEditor.; Grant Ryan E. guestEditor.
• Is Part Of: Concurrency and computation. Volume 32:Number 3(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-01-22
• Subjects: bulk synchronous parallel model -- graph data processing -- graph partition -- global synchronization -- MapReduce; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4432
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Graph data processing has been widely applied in a variety of domains such as industry, science, social network, and so on. It therefore has stimulated many efforts devoted to this area. To embrace the fast development trend of big graph data, graph data processing based on Pregel‐like systems has been regarded as one of the most promising ways and has widely attracted the attention of researchers. However, it still remains in its early stage and there still exist many challenges. In Pregel, the superstep synchronization is time consuming as the graph data iteration operation requires multiple synchronizations. Furthermore, the graph data partition strategy adopted by Pregel fails to support load balancing, therefore causing the increase of network I/O overhead as the scale of graph data grows. To address these issues, this paper presents an efficient computational framework for graph data processing based on the bulk synchronous parallel model. The global synchronization control mechanism is improved by determining the start time of the next round of superstep through counting the number of global message files. Furthermore, an improved graph data partition mechanism based on a balanced hash method is proposed to reduce the communication overhead between different partitions of sub‐graph computational tasks. We also re‐design the PageRank algorithm to verify the effectiveness of the proposed framework. Experimental results on different real‐world datasets verify the efficiency of our proposed framework as it outperforms Giraph (an open source Pregel‐like system) by 58 % −69 %, and achieves 10×−17× performance improvement over Hadoop.