Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (1): 132-139.DOI: 10.11772/j.issn.1001-9081.2021071219

• Data science and technology • Previous Articles    

Parallel pivoted subgraph matching with multiple coding trees on GPU

Yang WANG, Shijie JIANG, Yucong CAO, Chuanwen LI()   

  1. School of Computer Science and Engineering,Northeastern University,Shenyang Liaoning 110169,China
  • Received:2021-07-14 Revised:2021-08-18 Accepted:2021-08-23 Online:2022-01-11 Published:2022-01-10
  • Contact: Chuanwen LI
  • About author:WANG Yang, born in 1996, M. S. candidate. His research interests include data management.
    JIANG Shijie, born in 1996, M. S. candidate. His research interests include data management.
    CAO Yucong, born in 1997, M. S. candidate. His research interests include data management.
    LI Chuanwen, born in 1982, Ph. D., associate professor. His research interests include data management.
  • Supported by:
    National Natural Science Foundation of China(61872071)

多编码树GPU并行轴心子图匹配

汪洋, 江世杰, 曹宇聪, 李传文()   

  1. 东北大学 计算机科学与工程学院,沈阳 110169
  • 通讯作者: 李传文
  • 作者简介:汪洋(1996—),男,安徽芜湖人,硕士研究生,主要研究方向:数据管理
    江世杰(1996—),男,福建福州人,硕士研究生,主要研究方向:数据管理
    曹宇聪(1997—),男,河北保定人,硕士研究生,主要研究方向:数据管理
    李传文(1982—),男,山东烟台人,副教授,博士,CCF会员,主要研究方向:数据管理。

Abstract:

The subgraph isomorphism problem is a Non-deterministic Polynomial (NP)-complete problem, and the pivoted subgraph isomorphism is a special subgraph isomorphism problem. There are many existing efficient subgraph isomorphism algorithms, but there is no GPU-based search algorithm for the pivoted subgraph isomorphism problem at present, and a large number of unnecessary intermediate results will be generated when the pivoted subgraph matching problem is solved by the existing subgraph isomorphism algorithms. Therefore, a GPU-based pivoted subgraph isomorphism algorithm was proposed. Firstly, through a novel coding tree method, nodes were encoded by the combination of node labels, degrees and the structural features of node neighbors. And the query graph nodes were pruned on GPU in parallel, so that the size of search space tree generated by the data graph candidate nodes was significantly reduced. Then, the candidate nodes of the query graph node were visited level by level, and the unsatisfied nodes were filtered out. Finally, the obtained subgraph was verified whether it was an isomorphic subgraph of the query graph, and the search of pivoted subgraph isomorphism was realized efficiently. Experimental results show that compared with GPU-friendly Subgraph Matching (GpSM) algorithm, the proposed algorithm has the execution time reduced by one-half, and the proposed algorithm can efficiently perform the pivoted subgraph isomorphism search with scalability. The proposed pivoted subgraph isomorphism algorithm can reduce the time required to solve the pivoted subgraph isomorphism problem, while reducing GPU memory consumption and improving the performance of algorithm.

Key words: GPU, coding tree, pivoted subgraph isomorphism, subgraph isomorphism, parallel acceleration

摘要:

子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题。针对现在已经有许多高效的子图同构算法,然而对于轴心子图同构问题目前并没有基于GPU的搜索算法,且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出了一种基于GPU的轴心子图同构算法。首先,通过一种新颖的多编码树方式,利用节点的标签、度以及节点邻居的结构特征的组合对节点进行编码,并在GPU上对查询图节点并行地进行剪枝,从而明显地减小数据图候选节点所生成的搜索空间树的尺寸;然后,逐层访问查询图节点的候选节点,过滤掉不满足的节点;最后,验证得到的子图是否是查询图的同构子图,从而高效地完成轴心子图同构搜索。实验结果表明,与GPU友好子图匹配(GpSM)算法相比,所提算法的执行时间降低了二分之一,且该算法能够高效地执行轴心子图同构搜索并且具有可扩展性。所提轴心子图同构算法可以减少解决轴心子图同构问题所需的时间,同时降低了GPU内存消耗,提升了算法的性能。

关键词: GPU, 编码树, 轴心子图同构, 子图同构, 并行加速

CLC Number: