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

Keyword search algorithm of large graph based on GPU

作　　者：林鹤翔 乔连鹏 袁野 王国仁 LIN He-xiang;QIAO Lian-peng;YUAN Ye;WANG Guo-ren(School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China;School of Computer Science and Engineering,Northeastern University,Shenyang 110169,China)

机构地区：[1]北京理工大学计算机学院,北京100081 [2]东北大学计算机科学与工程学院,辽宁沈阳110169

出　　处：《浙江大学学报（工学版）》2022年第2期271-279,共9页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金资助项目(61932004,61732003,61729201);中央高校基本科研基金资助项目(N181605012)。

摘　　要：在传统图上关键字检索问题研究的基础上,基于图形处理器(GPU)设计新的关键字检索算法.基于Steiner tree语义定义关键字检索问题,针对该问题结合传统多源最短路径算法在CPU上设计基本算法,由于CPU架构特性,该算法无法直接移植到GPU上.提出GPU上的基本检索算法,分析它相对于CPU版本的优势和仍然存在的不足.为了提升算法查询速度,反思GPU上基本检索算法的不足之处,提出基于索引的优化技术,利用单源最短路径算法的松弛更新思想、关键字独立性和内部整体性,设计GPU上的高效关键字检索算法.扩展该算法思想,对r-cliques关键字检索问题提出GPU上的优化思路.通过分析算法复杂度并在真实数据集上进行实验,证明该GPU算法的正确性和有效性,并证明算法在较大规模图数据上仍有较强的计算性能.A new keyword search algorithm on graphics processing unit(GPU) was designed based on the research of the traditional keyword search problem on graphs. First of all, a keyword search problem based on Steiner tree semantics was defined. A basic algorithm was designed on the CPU in combination with the traditional all-pair shortest path algorithm. The algorithm could not be directly transplanted to the GPU due to the characteristics of the CPU architecture. Secondly, a basic search algorithm on GPU was designed, and its advantages and remaining shortcomings compared to the CPU version were analyzed. To improve the query speed of the algorithm, an indexbased optimization technique was proposed reflecting on the shortcomings of the basic search algorithm on GPU. An efficient keyword search algorithm on GPU was designed, using the relaxing and updating idea of the single-source shortest path algorithm, keyword independence, and internal integrity. Finally, an optimization idea on GPU for the r-cliques keyword search problem was proposed based on the idea of the algorithm. By analyzing the complexity of the algorithm and conducting experiments on real data sets, the correctness and effectiveness of the GPU algorithm are proved, and it is proved that the algorithm still has strong computing performance on large-scale graph data.

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

分 类 号：TP399[自动化与计算机技术—计算机应用技术]