Accelerating Subgraph Matching Using Isolated Vertices and BFS Data Structures
摘要
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.