基于GPU的大图数据上的关键字检索算法

• 作者: 林鹤翔 乔连鹏 袁野 王国仁
• 来源期刊: 浙江大学学报（工学版）
• 学科: 工学
• 关键词: 检索 属性图 索引 GPU通用计算 并行计算
• 年，卷（期）: 2022,（2）
• 所属期刊栏目: 计算机与控制工程|Computer and Control Engineering
• 页码范围: 271-279
• 页数: 9页
• 分类号: TP399
• 语种: 中文
• DOI: 10.3785/j.issn.1008-973X.2022.02.007

摘要

在传统图上关键字检索问题研究的基础上,基于图形处理器(GPU)设计新的关键字检索算法.基于Stein-er tree语义定义关键字检索问题,针对该问题结合传统多源最短路径算法在CPU上设计基本算法,由于CPU架构特性,该算法无法直接移植到GPU上.提出GPU上的基本检索算法,分析它相对于CPU版本的优势和仍然存在的不足.为了提升算法查询速度,反思GPU上基本检索算法的不足之处,提出基于索引的优化技术,利用单源最短路径算法的松弛更新思想、关键字独立性和内部整体性,设计GPU上的高效关键字检索算法.扩展该算法思想,对r-cliques关键字检索问题提出GPU上的优化思路.通过分析算法复杂度并在真实数据集上进行实验,证明该GPU算法的正确性和有效性,并证明算法在较大规模图数据上仍有较强的计算性能.