OnFlyP:基于定向边交换的分布式在线大图划分算法

随着大数据时代的到来,基于云环境的大图迭代计算已经成为新的研究热点,其中提高图划分算法的执行效率和降低划分后子图之间的通信边规模是改善计算性能的关键.已有工作主要分为离线划分和在线划分两大类,无法在执行效率和通信边规模方面同时满足迭代处理需求.文中针对真实世界的大图,提出了聚簇系数概念,定量分析了顶点分布的局部性,以此为基础设计了一种基于定向边交换模型的分布式在线图划分算法(OnFlyP),可在迭代计算的数据加载阶段快速完成图划分,同时通过出边的交换有效降低通信边规模,以满足迭代计算需求.OnFlyP采用实时控制和最小对称矩阵控制实现负载均衡,前者具有较高的执行效率,而后者对降低通信边规模有较好的优化效果,可根据实际应用的处理需求灵活选择.最后,作者使用多种真实数据验证了OnFlyP算法的有效性.