公开(公告)号：CN111737540A

公开(公告)日：2020-10-02

申请号：CN202010460064.5

申请日：2020-05-27

Applicant: 中国科学院计算技术研究所

Inventor： 聂娜 ,  王国波 ,  曹华伟 ,  叶笑春

IPC: G06F16/903 ,  G06F16/901

Abstract: 本发明实施例提供了一种图数据处理方法，包括：S1、获取包含多个顶点的图数据，按顶点的出度由小到大的顺序对顶点排序并将排序序号作为第一重排序ID；S2、根据第一重排序ID将图数据的顶点按预设粒度以轮询方式依次分配到分布式计算节点集群中的每一个分布式计算节点；S3、计算节点使用混合BFS算法对其获得的部分图数据进行遍历，每层遍历后各计算节点得到局部的下一层活跃顶点集；S4、每层遍历后相邻计算节点间进行环形通信以传递局部的下一层活跃顶点集，在部分层遍历后传递局部的下一层活跃顶点集之前，确定本次待传递的局部的下一层活跃顶点集的压缩方式，本发明通过顶点的出度对顶点ID进行重排序、数据压缩和环形通信，提高了通信效率。

公开(公告)号：CN111737540B

公开(公告)日：2022-11-29

申请号：CN202010460064.5

申请日：2020-05-27

Applicant: 中国科学院计算技术研究所

Inventor： 聂娜 ,  王国波 ,  曹华伟 ,  叶笑春

IPC: G06F16/903 ,  G06F16/901

Abstract: 本发明实施例提供了一种图数据处理方法，包括：S1、获取包含多个顶点的图数据，按顶点的出度由小到大的顺序对顶点排序并将排序序号作为第一重排序ID；S2、根据第一重排序ID将图数据的顶点按预设粒度以轮询方式依次分配到分布式计算节点集群中的每一个分布式计算节点；S3、计算节点使用混合BFS算法对其获得的部分图数据进行遍历，每层遍历后各计算节点得到局部的下一层活跃顶点集；S4、每层遍历后相邻计算节点间进行环形通信以传递局部的下一层活跃顶点集，在部分层遍历后传递局部的下一层活跃顶点集之前，确定本次待传递的局部的下一层活跃顶点集的压缩方式，本发明通过顶点的出度对顶点ID进行重排序、数据压缩和环形通信，提高了通信效率。