买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉湖南大学申请的专利一种基于GPU加速的可达性查询方法和系统获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN120011601B 。

龙图腾网通过国家知识产权局官网在2025-12-02发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202510088606.3，技术领域涉及：G06F16/901；该发明授权一种基于GPU加速的可达性查询方法和系统是由胡逸騉;张瑞;周旭;黄阳;李肯立设计研发完成，并于2025-01-21向国家知识产权局提交的专利申请。

本一种基于GPU加速的可达性查询方法和系统在说明书摘要公布了：本发明公开了一种基于GPU加速的可达性查询方法，包括：接收来自用户的图数据，对该图数据进行压缩预处理，以获取压缩处理后的图数据，获取来自用户的查询点，其包括源顶点和目标顶点，配置GPU的环境，在配置好的GPU环境中将压缩处理后的图数据以及查询点复制到GPU的内存中，计算图数据的平均出度，并判断该平均出度是否大于预先设置的阈值，如果是则获取复制到GPU的内存中的图数据，并使用两阶段BFS算法在该图数据中查询获取的查询点是否可达作为查询结果，然后将查询结果复制到CPU内存并输出。本发明能够解决现有基于索引的可达性查询算法由于构建用于可达性查询的索引需要消耗大量的存储资源，无法处理大规模图数据的技术问题。

本发明授权一种基于GPU加速的可达性查询方法和系统在权利要求书中公布了：1.一种基于GPU加速的可达性查询方法，其特征在于，包括以下步骤： 1接收来自用户的图数据，对该图数据进行压缩预处理，以获取压缩处理后的图数据； 2获取来自用户的查询点，其包括源顶点和目标顶点，配置GPU的环境，在配置好的GPU环境中将步骤1压缩处理后的图数据以及查询点复制到GPU的内存中； 3计算步骤2复制到GPU的内存中的图数据的平均出度，并判断该平均出度是否大于预先设置的阈值，如果是则进入步骤4，否则进入步骤5； 4获取步骤2复制到GPU的内存中的图数据，并使用两阶段BFS算法在该图数据中查询步骤2获取的查询点是否可达作为查询结果，然后转入步骤6；步骤4具体包括以下子步骤： 4-1创建顶点队列vque、边队列eque以及距离数组dis，将该顶点队列vque初始化为源顶点，将该边队列eque初始化为空，将距离数组dis中源顶点对应的距离初始化为0，将距离数组dis中其余顶点对应的距离初始化为无穷大； 4-2判断顶点队列vque是否为空，如果是则将源顶点和目标顶点不可达作为查询结果，过程结束，否则判断顶点队列vque中是否包含目标顶点，如果是则将源顶点和目标顶点可达作为查询结果，过程结束，否则进入步骤4-3； 4-3获取当前线程的全局ID； 4-4设置计数器global_id1＝步骤4-3得到的当前线程的全局ID； 4-5判断global_id1是否小于顶点队列vque的长度，若是则获取顶点队列vque中第global_id1个顶点vque[global-id1]，然后进入步骤4-6，否则表示顶点队列vque中所有顶点都已经处理完毕，然后进入步骤4-9； 4-6获取顶点队列vque中第global_id1个顶点vque[global-id1]对应的邻接表的大小，根据邻接表的大小获取该顶点对应的线程在所处的线程网格中对应的线程束内部的前缀和结果，作为第global_id1个顶点vque[global-id1]在对应的邻接表中的邻接顶点在边队列eque中的偏移量，并将所有邻接顶点存储到边队列eque中； 4-7设置global_id1＝global_id1+gridDim.x*blockDim.x，并返回步骤4-5；其中gridDim.x表示维度为x的线程所处的线程网格中线程块的数量，blockDim.x表示维度为x的线程对应的线程块中包含的线程数量，gridDim.x*blockDim.x表示维度为x的线程所处的线程网格中的线程总数； 4-8将步骤4-6得到的边队列eque复制到共享内存，在共享内存内利用哈希表进行对边队列eque进行冲突检测处理，以得到冲突检测处理后的边队列eque； 4-9设置计数器global_id2＝步骤4-3得到的当前线程的全局ID； 4-10判断global_id2是否小于边队列eque的长度，若是则获取边队列eque中第global_id2个顶点eque[global_id2]，然后进入步骤4-11，否则表示边队列eque中所有顶点都已经处理完毕，然后返回步骤4-2； 4-11判断距离数组dis中第global_id2个顶点eque[global_id2]对应的距离是否为无穷大，若是则更新第global_id2个顶点eque[global_id2]在距离数组dis中对应的距离，并将第global_id2个顶点eque[global_id2]加入顶点队列vque，否则进入步骤4-12； 4-12设置global_id2＝global_id2+gridDim.x*blockDim.x，并返回步骤4-10； 5获取步骤2复制到GPU的内存中的图数据，并使用双向BFS算法在该图数据中查询步骤2获取的查询点是否可达作为查询结果，然后转入步骤6； 6将查询结果复制到CPU内存并输出。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人湖南大学，其通讯地址为：410082 湖南省长沙市岳麓区麓山南路1号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。

以上内容由龙图腾AI智能生成。