分布式图计算系统和分布式图计算方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN110704693A(43)申请公布日2020.01.17(21)申请号201910924175.4(22)申请日2019.09.27(71)申请人清华大学地址100084北京市海淀区清华大学(72)发明人武永卫陈康姜进磊李雪章明星(74)专利代理机构北京睿邦知识产权代理事务所(普通合伙)11481代理人徐丁峰(51)Int.Cl.G06F16/901(2019.01)权利要求书2页说明书5页附图3页(54)发明名称分布式图计算系统和分布式图计算方法(57)摘要分布式图计算系统和方法，系统包括多个计算机和数据库，每台计算机上具有一个或多个计算结点，首先进行初始化，各个计算结点分别从数据库中读取不相交的原图的一部分边；主体计算流程，采用以子图为中心的迭代化计算方法，同时加入图缩减和重新划分过程以加速收敛，其中每轮迭代包含以下步骤：重新划分步骤，在每轮迭代的开始，首先对当前计算的图进行重新划分；本地计算步骤；缩减步骤，每个计算结点本地计算完成后，删除被判定无用的部分点/边，对原图进行重构；判断剩下的所有边是否能够存储在单个计算结点，为是的情况下，迭代结束，否则返回到重新划分步骤。本发明图计算方技术可以有效减少算法收敛所需的迭代轮数，提高计算效率。CN110704693ACN110704693A权利要求书1/2页1.一种分布式图计算系统，包括多个计算机和数据库，每台计算机上具有一个或多个计算结点，所述分布式图计算系统如下操作：在进行图算法的计算之前，首先进行初始化，各个计算结点分别从数据库中读取不相交的原图的一部分边，执行按边划分的划分方法；主体计算流程，采用以子图为中心的迭代化计算方法，同时加入图缩减和重新划分过程以加速收敛，其中每轮迭代包含以下步骤：重新划分步骤，在每轮迭代的开始，首先对当前计算的图进行重新划分，要求每个计算结点存储的边数不得少于一个用户定义的整数参数T，本地计算步骤，重新划分完成后，每个计算结点对其所存储的子图进行计算，缩减步骤，每个计算结点本地计算完成后，判断部分点/边的信息是否对后续的计算过程无用，删除被判定无用的部分点/边，对原图进行重构；判断剩下的所有边是否能够存储在单个计算结点，在判断结果为是的情况下，上述的分布式计算流程结束，否则返回到重新划分步骤。2.根据权利要求1的分布式图计算系统，其中在按边划分时，在整个分布式图计算系统中，每条边被保存且只被保存一次。3.根据权利要求1的分布式图计算系统，其中在按边划分时，存在被保存大于一次的点。4.根据权利要求1的分布式图计算系统，所述分布式图计算系统用于计算弱连通分量WCC、极大独立子集MIS、最小生成树MCST或三角形计数TC。5.根据权利要求4的分布式图计算系统，在计算弱连通分量WCC的情况下，每个计算结点本地的连通分量用一棵树的形状表达，对于每个本地WCC，选取一个共享点作为树的根，对于其他每个点，保存一条边连接这个点和其对应的树根。6.一种分布式图计算方法，在分布式图计算系统上进行，分布式图计算系统包括多个计算机和数据库，每台计算机上具有一个或多个计算结点，所述分布式图计算方法包括：在进行图算法的计算之前，首先进行初始化，各个计算结点分别从数据库中读取不相交的原图的一部分边，执行按边划分的划分方法；主体计算流程，采用以子图为中心的迭代化计算方法，同时加入图缩减和重新划分过程以加速收敛，其中每轮迭代包含以下步骤：重新划分步骤，在每轮迭代的开始，首先对当前计算的图进行重新划分，要求每个计算结点存储的边数不得少于一个用户定义的整数参数T，本地计算步骤，重新划分完成后，每个计算结点对其所存储的子图进行计算，缩减步骤，每个计算结点本地计算完成后，判断部分点/边的信息是否对后续的计算过程无用，删除被判定无用的部分点/边，对原图进行重构；判断剩下的所有边是否能够存储在单个计算结点，在判断结果为是的情况下，上述的分布式计算流程结束，否则返回到重新划分步骤。7.根据权利要求6的分布式图计算方法，其中在按边划分时，在整个分布式图计算系统中，每条边被保存且只被保存一次。8.根据权利要求6的分布式图计算方法，其中在按边划分时，存在被保存大于一次的点。2CN110704693A权利要求书2/2页9.根据权利要求6的分布式图计算方法，所述分布式图计算方法用于计算弱连通分量WCC、极大独立子集MIS、最小生成树MCST或三角形计数TC。10.根据权利要求9的分布式图计算方法，在计算弱连通分量WCC的情况下，每个计算结点本地的连通分量用一棵树的形状表达，对于每个本地WCC，选取一个共享点作为树的根，对于其他每个点，保存一条边连接这个点和其对应的树根。3CN110704693A说明书1/5页分布式图计算系