(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210397695.6 (22)申请日 2022.04.15 (71)申请人 中国科学院软件研究所 地址 100190 北京市海淀区中关村南四街 4 号 申请人 中国电力科 学研究院有限公司 (72)发明人 乔颖　赵新朋　王宏安　刘道伟　 赵高尚　冷昶　郭超平　 (74)专利代理 机构 北京君尚知识产权代理有限 公司 11200 专利代理师 司立彬 (51)Int.Cl. G06F 16/901(2019.01) G06F 9/50(2006.01) (54)发明名称 一种面向异质图数据的在线图划分方法 (57)摘要 本发明公开了一种面向异质图数据的在线 图划分方法， 其步骤包括： 1)评估图计算系统的 计算速度不平衡性和存储空间不平衡性； 根据图 计算系统进行异质图计算中不同类型节点的节 点函数时间复杂 度T确定图计算系统的计算速度 不平衡性； 根据图计算系统进行异质图计算中不 同类型节点所携带的数据占用的存储空间Sv和 不同类型边所携带的数据占用的存储空间Se确 定图计算系统的存储空间不平衡性； 2)根据不同 类型节点对应的节点函数时间复杂度T、 存储空 间Sv， 不同类型边对应的存储空间Se， 将当前待 处理的异质图数据分配到不同的分区上。 本发明 优化了图计算中的任务分配， 使图计算过程中负 载与内存使用更加均衡， 达到提升图计算运行效 率的结果。 权利要求书2页 说明书9页 附图2页 CN 114791965 A 2022.07.26 CN 114791965 A 1.一种面向异质图数据的在线图划分方法， 其 步骤包括： 1)评估图计算系统的计算速度不平衡性和存储空间不平衡性； 其中， 根据图计算系统 进行异质图计算中不同类型节点的节点函数时间复杂度T确定所述图计算系统的计算速度 不平衡性； 根据图计算系统进 行异质图计算中不同类型节点所携带的数据占用的存储空间 Sv和不同类型边所携带的数据占用的存储空间Se确定所述图计算系统的存储空间不平衡 性； 2)根据不同类型节点对应的节点函数时间复杂度T、 存储空间Sv， 不同类型边对应的存 储空间Se， 将当前待处 理的异质图数据分配到不同的分区上。 2.根据权利要求1所述的方法， 其特征在于， 将当前待处理 的异质图数据中的每条边只 分配到一个分区上， 同一节点分配到一个或多个分区上。 3.根据权利要求2所述的方法， 其特征在于， 步骤2)中， 对于当前待处理的异质图数据 分配到不同的分区上的方法为： 21)每当划分异质图G中的一条边e＝(vsrc,vdst)时， 首先计算其分配到分区集合P中每 个分区p上的得分 其 中， 复制分数 平衡 分数 A(v)表示已经有节点v的分区集合， δ(v)表 示节点v在当前分区上的部分度， v∈(vsrc,vdst)， vsrc为边e的起始节点， vdst为边e的终止节 点， 参数μ用来控制不同分区上的不平衡程度； maxsize和minsize是指当前所有分区中最 大、 最小占用存储空间， |p|是分区p上已有数据占用的存储空间； 遍历分区集合P中的所有 分区， 找出使得分CSGP‑HG(vsrc,vdst,p)取得最大值的分区p记为pmax， 将当前边e分配到该pmax 分区上， 然后根据分配结果更新|p|、 A(vsrc)、 A(vdst)、 δ(vsrc)、 δ(vdst)； 22)每当划分异质图G中的一个节点v时， 遍历分配集合P中的所有分区的节点函数耗 时， 将当前节点v分配到的使 取得最大值所对应的分区上； 然后 根据分配结果 更新对应分区的节点函数耗时； 其中， maxtime和 mintime分别表示分配集合P中的所有分区内已分配节点的最大、 最小节点函数耗时， pt表 示分区p内已分配节点的节点 函数耗时； 23)将划分好的节点和边组成图， 开始进行图计算迭代运 算； 24)重复步骤21)～ 23)， 处理完异质图G的所有边和节点， 完成对异质图G的划分。 4.根据权利要求3所述的方法， 其特征在于， |p|＝mem(e)+α*mem(vsrc)+β*mem(vdst), 其中， A(v)表示已经有节点v副本的分区集合， men (e)表示边e所占用的内存空间， men(v)表示节点v所占用的内存空间。 5.根据权利要求3所述的方法， 其特征在于， 使用集合维护A(v)， 当分配边e＝(vsrc, vdst)到分区p后， A(vsrc)＝A(vsrc)∪{p}， A(vdst)＝A(vdst)∪{p}。权　利　要　求　书 1/2 页 2 CN 114791965 A 26.根据权利 要求3所述的方法， 其特征在于， 在每个分区上使用HashMap维护 δ(v)， 当分 配边e＝(vsrc,vdst)到分区p后， p分区上的δ(vsrc)＝ δ(vsrc)+1, δ(vdst)＝ δ(vdst)+1。 7.根据权利要求1所述的方法， 其特征在于， 所述图计算系统为GAS模型， 其依次包括聚 集Gather、 计算Ap ply、 分发Scat ter三个阶段。 8.一种服务器， 其特征在于， 包括存储器和 处理器， 所述存储器存储计算机程序， 所述 计算机程序被配置为由所述处理器执行， 所述计算机程序包括用于执行权利要求1至7任一 所述方法中各步骤的指令 。 9.一种计算机可读存储介质， 其上存储有计算机程序， 其特征在于， 所述计算机程序被 处理器执行时实现权利要求1至7任一所述方法的步骤。权　利　要　求　书 2/2 页 3 CN 114791965 A 3