Improving large graph processing on partitioned graphs in the cloud

Rishan Chen*, Xuetian Weng, Bingsheng He, Mao Yang, Koon Kau CHOI, Xiaoming Li

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

40 Citations (Scopus)

Abstract

As the study of large graphs over hundreds of gigabytes becomes increasingly popular for various data-intensive applications in cloud computing, developing large graph processing systems has become a hot and fruitful research area. Many of those existing systems support a vertex-oriented execution model and allow users to develop custom logics on vertices. However, the inherently random access pattern on the vertex-oriented computation generates a significant amount of network traffic. While graph partitioning is known to be effective to reduce network traffic in graph processing, there is little attention given to how graph partitioning can be effectively integrated into large graph processing in the cloud environment. In this paper, we develop a novel graph partitioning framework to improve the network performance of graph partitioning itself, partitioned graph storage and vertex-oriented graph processing. All optimizations are specifically designed for the cloud network environment. In experiments, we develop a system prototype following Pregel (the latest vertex-oriented graph engine by Google), and extend it with our graph partitioning framework. We conduct the experiments with a real-world social network and synthetic graphs over 100GB each in a local cluster and on Amazon EC2. Our experimental results demonstrate the efficiency of our graph partitioning framework, and the effectiveness of network performance aware optimizations on the large graph processing engine.

Original languageEnglish
Title of host publicationProceedings of the 3rd ACM Symposium on Cloud Computing, SoCC 2012
DOIs
Publication statusPublished - 2012
Event3rd ACM Symposium on Cloud Computing, SoCC 2012 - San Jose, CA, United States
Duration: 14 Oct 201217 Oct 2012

Publication series

NameProceedings of the 3rd ACM Symposium on Cloud Computing, SoCC 2012

Conference

Conference3rd ACM Symposium on Cloud Computing, SoCC 2012
Country/TerritoryUnited States
CitySan Jose, CA
Period14/10/1217/10/12

Scopus Subject Areas

  • Software

User-Defined Keywords

  • Cloud computing
  • Data center network
  • Graph partitioning
  • Large graph processing

Fingerprint

Dive into the research topics of 'Improving large graph processing on partitioned graphs in the cloud'. Together they form a unique fingerprint.

Cite this