High Impact Factor : 4.396 icon | Submit Manuscript Online icon |

A Survey on Subgraph Matching Algorithm for Graph Database


Maninder Kaur Rajput , K.K.W.I.E.E.R., Nashik, Maharashtra, India; Dr. Prof. Snehal Kamalapur, K.K.W.I.E.E.R., Nashik, Maharashtra, India


Graph Database, Isomorphism, Offline Phase, Online Phase, Subgraph Matching


Subgraph matching is a technique to retrieve subgraphs which are isomorphic to query graph. A graph S (VS, ES) is subgraph of graph G (VG, EG) if VS ⊆ VG and ES ⊆ EG. Subgraph matching is a process to fetch all subgraphs S (VS, ES) from graph G (VG, EG) which are structurally isomorphic to input graph I(VI, EI) using subgraph matching algorithm. Subgraph matching is a NP-hard. In real-world graphs such as semantic web, social networks, protein interaction and biological networks, subgraph matching will retrieve subgraphs which are isomorphic to query graph from data graph. Many subgraph matching algorithms have proposed in recent years, these algorithms aims to find desired results in less time for real datasets using information like join orders, pruning techniques and vertex neighbour information. Subgraph matching algorithms can be classified into two clases: exact and approximate matching algorithms. These two approaches are being described in survey.

Other Details

Paper ID: IJSRDV3I120074
Published in: Volume : 3, Issue : 12
Publication Date: 01/03/2016
Page(s): 149-152

Article Preview

Download Article