基于 GPU 的子图匹配优化技术

An efficient graphic processing unit (GPU)-based subgraph matching algorithm GpSI was proposed, and the optimization schemes were designed for the filtering phase and the joining phase of the mainstream algorithms. In the filtering phase, a filtering algorithm based on the composite signatures was proposed, and the local quantitative and structural features of the vertices were used to improve the filtering ability of the candidate sets. In the joining phase, a joining strategy based on candidate vertices was adopted. The space was pre-allocated at the granularity of the minimum number of neighbors, an efficient set operations was designed to realize the joining, and the extra overhead caused by the repeated joins in the traditional method was avoided. Experimental results of multiple datasets show that GpSI has obvious advantages in the filtering ability of the candidate set, the execution time, the GPU memory usage and the stability compared with the mainstream GPU subgraph matching algorithms. In a real data set experiment, the execution time of GpSI was 2 to 10 times faster compared to the execution time of GPU-friendly subgraph isomorphism algorithm.