Subgraph matching is a fundamental problem in graph analysis, with widespread applications in social networks, bioinformatics, and knowledge engineering. Traditional subgraph matching algorithms typically rely on backtracking search and recursive computation, which often lead to high computational complexity and an exponential growth of the search space when dealing with large scale graph data. This paper proposes ADR-IVE(AuxiliaryDualReorder-IVE) subgraph matching algorithm based on a backtracking enumeration framework, aiming to enhance the efficiency of subgraph matching and optimize query processing performance. The proposed method leverages the attributes of both the data graph and the query graph to optimize the generation order of query graph vertices, thereby effectively reduce the candidate space of query vertices. Experimental results demonstrate that the proposed method achieves an overall performance improvement of approximately 60% compared to state-of-the-art algorithms when handling large-scale and structurally complex subgraph matching tasks. This significant advantage highlights the method’s potential for widespread application and practical value in large-scale subgraph matching tasks.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Accelerating Subgraph Matching Using Isolated Vertices and BFS Data Structures

  • Guiyang Zhang,
  • Bo Ning,
  • Xin Zhou

摘要

Subgraph matching is a fundamental problem in graph analysis, with widespread applications in social networks, bioinformatics, and knowledge engineering. Traditional subgraph matching algorithms typically rely on backtracking search and recursive computation, which often lead to high computational complexity and an exponential growth of the search space when dealing with large scale graph data. This paper proposes ADR-IVE(AuxiliaryDualReorder-IVE) subgraph matching algorithm based on a backtracking enumeration framework, aiming to enhance the efficiency of subgraph matching and optimize query processing performance. The proposed method leverages the attributes of both the data graph and the query graph to optimize the generation order of query graph vertices, thereby effectively reduce the candidate space of query vertices. Experimental results demonstrate that the proposed method achieves an overall performance improvement of approximately 60% compared to state-of-the-art algorithms when handling large-scale and structurally complex subgraph matching tasks. This significant advantage highlights the method’s potential for widespread application and practical value in large-scale subgraph matching tasks.