关键词: 图计算, 图迭代, 分布式计算, 同步迭代, 弱一致异步迭代

Abstract: The time and space complexity of many accurate algorithms is difficult to meet the realistic demands, while approximating algorithms are alternative choices. Iterative computing is an effective approximating method in numerical computing. A variety of algorithms and models can be classified into it. With the increase of data scale, iterative algorithms are blooming and developing. Graph computing is a natural way to express and analyze relationships. There are numerous graph algorithms being described as iterative models. Parallel iterating is regular in large graph computing. Graph iterating methods have different parallel execution models. Most of the existing parallel graph computing implementations are synchronous, and a few of them are asynchronous models. However, there are few studies about consistency constraints in graph iterating. In this paper, we discuss the iterative computing technique in graph computing model. We analyze the applicability of synchronous and asynchronous iterations, and study the asynchronous iterative methods under different consistency, as well as experimental proving. We propose an adaptive asynchronous execution model which is weakly consistent. It overcomes the shortcomings of existing asynchronous iterative methods. Experiments of this model were done in parallel and have shown that the model can effectively improve some graph algorithms, especially the iterating and converging speed.

Key words: graph computing, graph iteration, distributed computing, synchronous iterating, weakly consistent asynchronous iterating