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

摘要：

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

关键词：检索;属性图;索引;GPU通用计算;并行计算

所属期刊栏目：56

分类号：TP399(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;中央高校基本科研基金资助项目

在线出版日期：2022-03-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：271-279