Advanced Search
    Leng Fangling, Liu Jinpeng, Wang Zhigang, Chen Changning, Bao Yubin, Yu Ge, Deng Chao. Edge Cluster Based Large Graph Partitioning and Iterative Processing in BSP[J]. Journal of Computer Research and Development, 2015, 52(4): 960-971. DOI: 10.7544/issn1000-1239.2015.20131343
    Citation: Leng Fangling, Liu Jinpeng, Wang Zhigang, Chen Changning, Bao Yubin, Yu Ge, Deng Chao. Edge Cluster Based Large Graph Partitioning and Iterative Processing in BSP[J]. Journal of Computer Research and Development, 2015, 52(4): 960-971. DOI: 10.7544/issn1000-1239.2015.20131343

    Edge Cluster Based Large Graph Partitioning and Iterative Processing in BSP

    • With the development of Internet and the gradual maturity of related techniques in recent years, the processing of large graphs has become a new hot research topic. Since it is not appropriate for traditional cloud computing platforms to process graph data iteratively, such as Hadoop, researchers have proposed some solutions based on the BSP model, such as Pregel, Hama and Giraph. However, since graph algorithms need to frequently exchange intermediate results in accordance with the graph’s topological structure, the tremendous communication overhead impacts the processing performance of systems based on the BSP model greatly. In this paper, we first analyze the solutions proposed by the well-known BSP-based systems in reducing communication overhead, and then propose a graph partition strategy named edge cluster based vertically hybrid partitioning (EC-VHP), building a cost benefit model to study its effectiveness to the communication overhead. Then based on EC-VHP, we propose a vertex-edge computation model, and design both a plain hash index structure and a multi-queue parallel sequential index structure to further improve the processing efficiency of message communication. Finally, our experiments on real and synthetic data sets demonstrate the efficiency and accuracy of the EC-VHP and the index mechanism.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return