A Survey on Subgraph Matching Algorithm for Graph DatabaseJournal: International Journal for Scientific Research and Development | IJSRD (Vol.3, No. 11)
Publication Date: 2016-02-01
Authors : Maninder Kaur Rajput; Snehal Kamalapur;
Page : 149-152
Keywords : 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 Latest Articles
Last modified: 2016-02-12 19:15:53