图计算中基于一致性约束条件的迭代模型研究

来源：计算机研究与发展杂志2019年第2期北京时间：

作者：孙茹君,张鲁飞,郝子宇,陈左宁,

摘要：迭代计算是数值计算中有效的逼近方式，能够拟合多种计算模型.在大数据分析领域尤其是图计算中，迭代计算能够抽象描述大部分图算法，对结构化数据挖据和关联分析至关重要.随着数据规模的增长，很多精确算法的时空复杂度已经难以满足现实需求，迭代计算的算法越来越丰富.并行迭代是图计算的主要实现形式，已有的图并行策略大多数是同步模型，少量异步模型，对于一致性约束条件下的迭代研究较少.研究内容重点关注图计算模型中迭代执行技术，分析了同步迭代和异步迭代的适用性，以及不同一致性下的异步迭代方式，针对已有异步迭代方式的不足提出了自适应的弱一致异步执行模型，并进行了验证性实验.实验证明：该模型能有效提高部分图算法的执行效率，尤其是收敛速度和效果.

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