ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

A Survey on Subgraph Matching Algorithm for Graph Database

Journal: International Journal for Scientific Research and Development | IJSRD (Vol.3, No. 11)

Publication Date:

Authors : ; ;

Page : 149-152

Keywords : Graph Database; Isomorphism; Offline Phase; Online Phase; Subgraph Matching;

Source : Downloadexternal Find it from : Google Scholarexternal


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.

Last modified: 2016-02-12 19:15:53