BSP模型下基于边聚簇的大图划分与迭代处理

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

作者：冷芳玲,刘金鹏,王志刚,陈昌宁,鲍玉斌,于戈,邓超,

摘要：近年来随着互联网的普及和相关技术的日益成熟，大规模图数据处理成为新的研究热点.由于传统的如Hadoop等通用云平台不适合迭代式地处理图数据，研究人员基于BSP模型提出了新的处理方案，如Pregel，Hama，Giraph等.然而，图处理算法需要按照图的拓扑结构频繁交换中间计算结果而导致巨大的通信开销，这严重地影响了基于BSP模型的系统的处理性能.首先从降低消息通信的角度分析当前主流BSP系统的处理方案，然后提出了一种基于边聚簇的垂直混合划分策略(EC-VHP)，并建立代价收益模型分析其消息通信优化的效果.在EC-VHP的基础上，提出了一个点-边计算模型，并设计了简单Hash索引和多队列并行顺序索引机制，进一步提高消息通信的处理效率.最后，在真实数据集和模拟数据集上的大量实验，验证了EC-VHP策略和索引机制的正确性和有效性.

关键词：大规模图, BSP模型, 图划分, 点-边计算模型, 索引结构,