DualIso: An Algorithm for Subgraph Pattern Matching on Very Large Labeled Graphs

Graph pattern matching

Graph pattern matching은 주어진 data graph 내의 모든(또는 일정 수 이상의) 유사한 구조와 labelings를 가지고 있는 subgraph를 찾는다. Pattern matching algorithms은 graph 처리 query 시스템에서 사용할 수 있다.

---

As mentioned, one of the motivations for the evolvement of faster subgraph isomorphism algorithms is for their use in processing queries on graph databases. In [5], the authors present a basic outline for a graph pattern matching algorithm that could be used for this purpose as follows

(assuming query graph Q(Vq, Eq, lq) and vertices 0, ..., |Vq| − 1)

1) Retrieve feasible matches for each vertex in the query graph based on semantic and/or neighborhood information in the data graph. This results in sets Φ(0), ..., Φ(|Vq|−1), where Φ(u) is the set of feasible matches for vertex u ∈ Vq.

2) (Optional) Reduce the search space globally, refining the set of feasible matches for each query vertex.

3) (Optional) Optimize the search order of vertices in the query.

4) Search the remaining space in a depth-first manner.