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)


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

  1. 东北大学 计算机科学与工程学院,沈阳 110169
  • 通讯作者: 李传文
  • 作者简介:汪洋(1996—),男,安徽芜湖人,硕士研究生,主要研究方向:数据管理


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



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

CLC Number: