A Research On Graph Computation Platform In A Single PC By Application Of Graph Algorithm Tuned Graph Representation Format

Graph can be used to describe the connenction between entities, and analyze real-world problem, such as friend recommendation and web page ordering, by abstracting entity as vertex and connencion as edge. Tranditional graph algorithms assume the input graph fits in the memory of a single machine. However, the large-scale graphs, such as Web Graph and Social Network, break the assumption. Then, we naturally turn to cloud computing and distributed graph algorithms, such as Hadoop, for their scalability, ease of accessibility and fault tolerance. While the problems of cloud computing remain to be solved, such as control and reliability, data security, unpredicted cost and the difficulty of distributed algorithms for debugging and optimizing.Based on this situation, analytics over large-scale graph processing on a single PC reasonably is beginning to attract significant attention in the research community. Presented graph-computing platform on a single PC, such as GraphChi, Turbo Graph, can analyze large-scale graph efficiently. But they still have performance and ease abstraction of graph algorithm problem and can be optimized someway.This paper design and realize a graph computing platform on a single PC called HybridGraph based on GraphChi by the research on(1) Graph Algorithm tuned on Graph Representation Format,(2) Parallelism of CPU processing and I/O processing, and(3) Usage of Memory. And the experiment shows improvement on performance and abstraction of graph algorithm.The primary work of this paper includes:(I) Explored and classified the abstraction of graph algorithm, and summarized the graph algorithm and best-fit graph format;(II) Prove that the performance of graph processing can be improved by combination graph algorithm and graph format;(III) implementation of HybridGraph based on the open source GraphChi.