计算机研究与发展

作者：史惠康,王泽胜,胡克坤,董刚,赵有健,

关键词：大图, 流式划分, 分布式, 缓冲, 重流,

图划分是大图并行处理关键技术之一.现有图划分算法存在划分质量和效率难以平衡的问题，主要体现在离线划分算法划分质量高但耗时长；在线（也称流式）划分算法相对高效但划分质量不理想.为此，提出一种带缓冲区的分布式流式划分算法.该算法采用多加载器-多划分器架构，多个加载器并行读取图数据，提高图数据加载效率；每个划分器维护一个缓冲区，缓存相应加载器发来的图顶点，并按顶点度数高低排序，为划分器提供更多决策依据.划分器预置有4条流式启发式规则，围绕不同目标，对缓冲区中的顶点实施并行划分，并借助重流机制微调划分结果，改进划分质量.分布式系统环境下的划分质量与性能实验表明：提出算法的划分质量（割边比）比当前最好的在线划分算法改善超过18.8个百分点，并将图数据加载时间在划分总时间的占比，从单划分器-单加载器架构流式划分算法的平均30.8%缩减至平均20.1%.

来源：2025年第7期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2025年第7期