OnFlyP：基于定向边交换的分布式在线大图划分算法
随着大数据时代的到来，基于云环境的大图迭代计算已经成为新的研究热点，其中提高图划分算法的执行效率和降低划分后子图之间的通信边规模是改善计算性能的关键。已有工作主要分为离线划分和在线划分两大类，无法在执行效率和通信边规模方面同时满足迭代处理需求。文中针对真实世界的大图，提出了聚簇系数概念，定量分析了顶点分布的局部性，以此为基础设计了一种基于定向边交换模型的分布式在线图划分算法（OnFlyP），可在迭代计算的数据加载阶段快速完成图划分，同时通过出边的交换有效降低通信边规模，以满足迭代计算需求。 OnFlyP 采用实时控制和最小对称矩阵控制实现负载均衡，前者具有较高的执行效率，而后者对降低通信边规模有较好的优化效果，可根据实际应用的处理需求灵活选择。最后，作者使用多种真实数据验证了 OnFlyP 算法的有效性。
在线大图划分、边交换、实时控制、最小对称矩阵
TP311(计算技术、计算机技术)
国家“九七三”重点基础研究发展规划项目基金2012CB316201;国家自然科学基金61272179，61472071，61173028;中央高校基本科研业务费专项资金重点课题N120816001;教育部博士点基金20120042110028;教育部-中国移动科研基金项目MCM20125021资助．This research was supported by the National Basic Research Program 973 Program of China under Grant No．2012CB316201，the National Natural Science Foundation of China under Grant Nos．61272179，61472071，61173028， the Fundamental Research Funds for t
2015-10-08（万方平台首次上网日期，不代表论文的发表时间）
共14页
1838-1851
