Keyword search algorithm of large graph based on 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 index-based 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. Copyright ©2022 Journal of Zhejiang University (Engineering Science). All rights reserved.