Research On Optimization Method Of Graph-oriented Computation

As a complex data structure,graph is often used to model problems in real world.Due to the arrival of the “big data”,the scale of real-world graphs is increasing rapidly and quickly exceeds the memory capacity of standalone computer.To be able to process large graphs within limited memory,researchers have proposed many out-of-core(disk-based)graph processing systems which enable users to process large scale graphs without distributed clusters or machines with large memory.What’s more,these out-of-core graph systems also provide friendly programming interfaces which are convenient to use for users.However,the disadvantages in these system are obvious: use vertex id based method to partition a graph into subgraphs,ignoring the neighboring relationship between vertices in the graph;In each iteration,every vertex in each subgraph is processed only once which results in slow message propagation and many redundant iterations.To solve these problems,we propose the block update method in out-of-core environment and implement it on GraphChi(the new system is called BlockGraphChi).We also propose a directed multi-level graph partitioning method.With the help of the block update method in out-of-core environment,it requires only one iteration to propagate a newly generated message to all reachable vertices in a subgraph during the execution of graph algorithms,thus accelerating the convergence of graph algorithms and reducing the number of iterations required for algorithm’s convergence.By using the directed multi-level graph partitioning method which takes into account the structure of real-world graphs and edge direction,vertices inside a subgraph are more closely connected and edge direction between subgraphs becomes more consistent facilitating propagation of new messages and avoiding the excessive disk I/Os of subgraphs.The experiment results show that BlockGraphChi has better performance than GraphChi due to block update in out-of-core environment.Under the same experimental condition,the convergence speed of graph algorithms in BlockGraphChi is up to 30.4X faster than that in GraphChi and the number of iteration is reduced by 98.1% at most.For fixed-point graph algorithms with block update method,the directed multi-level graph partitioning method still yields performance advantages while other partitioning methods(hash and METIS)are not working.