  Subgraph matching, which finds subgraphs isomorphic to a query, is the key to
information retrieval from data represented as a graph. To avoid redundant
exploration in the data, existing methods restrict the search space by
extracting candidate vertices and candidate edges that may constitute
isomorphic subgraphs. However, it still requires expensive computation because
candidate vertices induce many subgraphs that are not isomorphic to the query.
In this paper, we propose GuP, a subgraph matching algorithm with pruning based
on guards. Guards are a pattern of intermediate search states that never find
isomorphic subgraphs. GuP attaches a guard on each candidate vertex and edge
and filters out them adaptively to the search state. The experimental results
showed that GuP can efficiently solve various queries, including those that the
state-of-the-art methods could not solve in practical time.

Databases;Data Structures and Algorithms;Information Retrieval