i2Graph: An Incremental Iterative Computation Model for Large Scale Dynamic Graphs
i2Graph: An Incremental Iterative Computation Model for Large Scale Dynamic Graphs
复制标题
DOI：
10.1109/ispa-bdcloud-sustaincom-socialcom48970.2019.00099
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Zhuo Tang;Mengsi He;Li Yang-;Zhongming Fu
中科院分区：
文献类型：
--
作者：
Zhuo Tang;Mengsi He;Li Yang-;Zhongming Fu
由于图数据集的快速变化，挖掘出来的信息很快就会过时，因此需要从头开始对整个数据集进行重新计算，这会造成计算时间和资源的浪费。为了减少这种计算的成本，本文提出了一种称为i2 Graph的模型来支持动态图的增量迭代计算。与传统的迭代方式不同，i2 Graph通过重用上一个图的结果来执行图算法，并对图中发生变化的部分进行计算。i2 Graph包含两个组件：（1）增量迭代计算模型，用于提高迭代图算法的执行效率;（2）增量更新方法，用于加速迭代图算法内的迭代过程。它是基于Spark GraphX实现的，Spark GraphX是一种流行的并行和分布式计算框架，用于大规模图形处理。实验结果验证了i2 Graph模型在对动态图进行一些迭代图算法时，与传统的迭代算法相比的性能优势。
Due to the rapid changes in graph data sets, the mined information will quickly become obsolete, thus the entire data set needs to be re-computed from the beginning, which will result in the waste of computing time and resources. To reduce the cost of such computations, this paper proposes a model called i2Graph to support incremental iterative computation for dynamic graphs. Different from the way of traditional iteration, i2Graph executes the graph algorithm by reusing the results of the previous graph and performs computation on parts of the graph that has changed. i2Graph contains two components: (1) an incremental iterative computation model to improve the execution efficiency of the iterative graph algorithm; and (2) an incremental update method to accelerate the iterative process within the iterative graph algorithm. It is implemented based on Spark GraphX, a popular parallel and distributed computing framework for large-scale graph processing. Experiment results verify the performance advantages of i2Graph model when performing some iterative graph algorithms on the dynamic graph, compared with the traditional iteration.