欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2021107208585
申请人: 湖南大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种用于减少通信开销的索引构建方法,其特征在于,所述方法包括:服务器接收终端发送的索引构建消息;

服务器响应所述索引构建消息,获取初始图数据和计算节点数量,将所述初始图数据转换为DAG图,根据所述计算节点数量和预设分区算法,确定所述DAG图中各顶点的分区,得到所述DAG图的分区结果,将所述DAG图按照所述分区结果部署至预设分布式图计算系统,得到各DAG分区的图数据结构,所述DAG图的分区结果中的分区数量基于所述计算节点数量确定;

服务器对各DAG分区中的顶点进行排序,得到各顶点的排序值;

服务器根据所述各DAG分区的图数据结构、所述顶点的排序值以及预设分布式图计算系统的计算模型,并行构建各所述DAG分区的内部点的2‑hop索引和边界点的2‑hop索引,所述边界点的2‑hop索引用于图数据的可达性查询;

服务器基于所述边界点的2‑hop索引,重构各DAG分区的边界点之间的路径;

服务器根据所述各DAG分区的图数据结构和所述各DAG分区的边界点之间的路径,构建边界图;

服务器基于所述边界图,重构边界点的2‑hop索引、并将重构后的边界点的2‑hop索引划分至各边界点所在的DAG分区,以进行分布式批量可达性查询;

整合内部点的2‑hop索引和重构后的边界点的2‑hop索引,并将整合后的内部点的2‑hop索引和重构后的边界点的2‑hop索引写入文件中进行存储记录。

2.根据权利要求1所述的索引构建方法,其特征在于,所述图数据结构包括顶点的度值和身份编号;所述对各DAG分区中的顶点进行排序,得到各顶点的排序值包括:确定各DAG分区中顶点的顶点类型;

根据所述顶点类型、所述度值以及所述身份编号,对各DAG分区中的顶点进行排序,得到各顶点的排序值。

3.根据权利要求2所述的索引构建方法,其特征在于,所述根据所述顶点类型、度值以及身份编号,对各DAG分区中的顶点进行排序,得到各顶点的排序值包括:根据所述顶点类型、所述度值以及所述身份编号,按照预设的由顶点类型、度值以及身份编号构成的优先级顺序,对各DAG分区中的顶点进行排序,得到各顶点的排序值。

4.根据权利要求1至3任意一项所述的索引构建方法,其特征在于,基于所述边界图,重构边界点的2‑hop索引、并将重构后的边界点的2‑hop索引划分至各边界点所在的DAG分区包括:在单个DAG分区内基于所述边界图,重构边界点的2‑hop索引、并将重构后的边界点的

2‑hop索引划分至各边界点所在的DAG分区;

或,在各个DAG分区内基于所述边界图,重构边界点的2‑hop索引,删除各DAG分区中不属于自身分区的重构后的边界点的2‑hop。

5.根据权利要求1至3中任一项所述的索引构建方法,其特征在于,基于所述边界图,重构边界点的2‑hop索引包括:基于所述边界图,结合所述边界图对应的图数据结构、所述各顶点的排序值以及所述预设分布式图计算系统的计算模型,重构所述边界点的2‑hop索引。

6.一种用于减少通信开销的索引构建装置,其特征在于,部署于服务器,所述装置包括:分区结果获取模块,用于接收终端发送的索引构建消息;

响应所述索引构建消息,获取初始图数据和计算节点数量,将所述初始图数据转换为DAG图,根据所述计算节点数量和预设分区算法,获取DAG图的分区结果,将所述DAG图按照所述分区结果部署至预设分布式图计算系统,得到各DAG分区的图数据结构,所述DAG图的分区结果中的分区数量基于所述计算节点数量确定;

顶点排序模块,用于对各DAG分区中的顶点进行排序,得到各顶点的排序值;

索引并行构建模块,用于根据所述各DAG分区的图数据结构、所述顶点的排序值以及预设分布式图计算系统的计算模型,并行构建各所述DAG分区对应的内部点的2‑hop索引和边界点的2‑hop索引,所述边界点的2‑hop索引用于图数据的可达性查询;

路径重构模块,用于基于所述边界点的2‑hop索引,重构各DAG分区的边界点之间的路径;

边界图构建模块,用于根据所述各DAG分区的图数据结构和所述各DAG分区的边界点之间的路径,构建边界图;

边界点索引重构模块,用于基于所述边界图,重构边界点的2‑hop索引、并将重构后的边界点的2‑hop索引划分至各边界点所在的DAG分区,以进行分布式批量可达性查询;

索引整合存储模,用于整合内部点的2‑hop索引和重构后的边界点的2‑hop索引,并将整合后的内部点的2‑hop索引和重构后的边界点的2‑hop索引写入文件中进行存储记录。

7.根据权利要求6所述的装置,其特征在于,所述图数据结构包括顶点的度值和身份编号;

所述顶点排序模块还用于确定各DAG分区中顶点的顶点类型,根据所述顶点类型、所述度值以及所述身份编号,对各DAG分区中的顶点进行排序,得到各顶点的排序值。

8.根据权利要求7所述的装置,其特征在于,所述顶点排序模块还用于根据所述顶点类型、所述度值以及所述身份编号,按照预设的由顶点类型、度值以及身份编号构成的优先级顺序,对各DAG分区中的顶点进行排序,得到各顶点的排序值。

9.一种计算机设备,包括存储器和处理器,所述存储器存储有计算机程序,其特征在于,所述处理器执行所述计算机程序时实现权利要求1至5中任一项所述的方法的步骤。

10.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器执行时实现权利要求1至5中任一项所述的方法的步骤。