面向动态大图异步增量计算的优化设计开题报告

1. 研究目的与意义（文献综述）

1.1研究目的

异步增量计算是支持动态大图处理的有效方式。然而在社交网络中，多个图顶点的状态可能同时发生变化，因此需要有效定义状态变化值的传递方式，加快收敛速度减少通信开销。对数据进行分区是目前行之有效的方法之一。

一般来说，为了快速地对大图进行处理，常常会使用分布式并行计算的思想，分布式图处理系统随着问题规模的扩大具有很好的拓展性，但是在提高系统处理效率方面仍然面临许多挑战^[1]。比如图的划分，要提高系统性能需要在保证集群各节点负载均衡的情况下，使得集群内各节点的通信量最少，是一个np难问题^[2]。此外，一个分布式系统需要解决集群内各节点协同工作、容错等一系列问题，而这类问题对系统的性能有重要的影响。

2. 研究的基本内容与方案

2.1研究内容

（1）数据划分

动态大图的图形数据的边和节点时刻发生改变，大图不同分区之间的数据访问会消耗很多的系统开销，因此需采用基于数据局部性的数据划分。对动态大图进行有效地分区存储，再对划分后的数据源进行计算，可以使计算结果重复使用，尽可能的减少了不必要地通讯开销。

3. 研究计划与安排

2016.01.11--2016.01.22：查阅参考文献，明确选题。

2016.01.23--2016.03.07：进一步查阅有关的参考资料，并分析总结；确定技术路线，并完成开题报告，提交给指导老师。

2016.03.08--2016.04.26：翻译英文资料（不少于5000汉字）；熟悉所选用的开发平台，进行需求分析，系统设计或算法设计，系统的编码工作。

4. 参考文献（12篇以上）

[1] 吴城文，张广艳，郑纬民. 从系统角度审视大图计算. 清华大学计算机科学与技术系,北京,2015.

[2] incoop: mapreducefor incremental computations.

[3] yanfeng zhang, shimin chen,qiang wang, and ge yu. i 2 mapreduce: incrementalmapreduce for mining evolving big data. 1041-4347 (c) 2015ieee.