Earticle

초록

영어

Processing very large graphs efficiently is a challenging task. Distributed graph processing systems process the billion-scale graphs efficiently but incur overheads of partitioning and distribution of the large graph over a cluster of nodes. In order to overcome these problems a disk-based engine, GraphChi was proposed recently that processes the graph in chunks on a single PC. GraphChi significantly outperformed all the representative distributed processing frameworks. Still, we observe that GraphChi incurs some serious degradation in performance due to 1) high number of non-sequential I/Os for processing every chunk of the graph; and 2) limited parallelism to process the graph. In this paper, we propose a novel engine named BiShard Parallel Processor (BSPP) to efficiently process billions-scale graphs on a single PC. We introduce a new storage structure BiShard. BiShard divides the large graph into subgraphs and maintains the in and out edges separately. This storage mechanism significantly reduces the number of non-sequential I/Os. We implement a new processing model named BiShard Parallel (BSP) on top of Bishard. BSP exploits the properties of Bishard to enable full CPU parallelism for processing the graph. Our experiments on real large graphs show that our solution significantly outperforms GraphChi.

목차

Abstract
 1. Introduction
 2. Related Work
 3. Preliminaries
  3.1. Disk-based processing
  3.2. Vertex-centric approach
  3.3. Parallel Sliding Window
 4. BiShard Parallel Processor
  4.1. Notions
  4.2. BiShard storage structure
  4.3. BiShard Parallel (BSP) processing model
  4.4. I/Os cost analysis
 5. Experimental Evaluation
  5.1. Experiments setup
  5.2. Page rank algorithm
 6. Conclusion
 Acknowledgements
 References

키워드

저자

• Kamran Najeebullah [ Department of Electronics and Computer Engineering Kyung Hee University, Korea ]
• Kifayat Ullah Khan [ Department of Electronics and Computer Engineering Kyung Hee University, Korea ]
• Waqas Nawaz [ Department of Electronics and Computer Engineering Kyung Hee University, Korea ]
• Young-Koo Lee [ Department of Electronics and Computer Engineering Kyung Hee University, Korea ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Multimedia and Ubiquitous Engineering

• 간기

  월간

• pISSN

  1975-0080

• 수록기간

  2008~2016

• 등재여부

  SCOPUS

• 십진분류

  KDC 505 DDC 605