BSP中基于边缘聚类的大图划分和迭代处理

由于传统的如Hadoop等通用云平台不适合重复式地处理图数据，研究人员基于BSP模型提出了新的处理方案，如Pregel，Hama，Giraph等。然而，图处理算法需要按照图的拓扑结构交换交换中间计算结果而导致巨大的通信开销，这严重地影响了基于BSP模型的系统的处理性能。首先从降低消息通信的角度分析当前主流BSP系统的处理方案，然后提出了一种基于边聚簇的垂直混合划分策略（EC-VHP），并建立收益模型分析其消息通信优化的效果。在EC‐VHP的基础上，提出了一个点‐边计算模型，并设计了简单的哈希索引和多序列并行顺序索引机制，进一步提高了消息通信的处理效率。最后，在真实数据集和模拟数据集上大量实验，验证了EC‐VHP策略和索引机制的正确性和有效性。