一种基于块的子图构建及分布式图处理方法

摘要

本发明公开了一种基于块的子图构建及分布式图处理方法，其子图构建方法，包括图分割、对子图中的顶点重新贴标签、将区间与数据片关联、分块和构建子图的步骤；采用启发式的、轻量级的SGP方法进行图分割，采用用户定义的启发式函数把顶点按顺序指派到P个子图，具有性能高，边的切割率较低的特点，并且可以兼顾子图工作负载平衡问题；其分布式图处理系统，块分割之后，子图之间以整个内存块为单位进行通信；与现有技术的细粒度通讯方式相比，本发明的基于内存块的数据交换，可以充分利用网络带宽，提高网络的利用率，降低通讯时间。

主权项

一种基于块的子图构建方法，其特征在于，具体包括以下步骤：(1)采用启发式函数将顶点按顺序指派到P个子图；P>1；(2)依次对P个子图的顶点贴标签，使之形成P个连续但不相交的区间；(3)将区间与数据片关联，并将数据片从0到(P‑1)按顺序贴上标签；每个数据片存放其目标顶点在该区间的边；(4)根据数据片中边的源顶点所属的区间把一个数据片分解成P个连续块；将块按顺序从0到(P‑1)贴标签；每个块用B(x,y)来标识，x是块标签号，y是是数据片标签号；0≤x≤P‑1，0≤y≤P‑1；(5)由一个局部边块、(P‑1)个远程入边块和(P‑1)个远程出边块构建成一个子图。