A graph is a symbolic representation of data and its relationships. It is used in many domains like bioinformatics, semantic web and chemical structures applications. Subgraph matching is a technique to retrieve set of subgraphs from dataset which are similar to query/input graph. Subgraph matching is a NP-hard. Graph S(VS, ES) is subgraph of graph G(VG ,EG ) if VS ? VG and ES ? EG. Work here aims to fetch all subgraphs S(VS, ES) from graph G(VG ,EG ) which are similar to query graph Q(VQ, EQ) using subgraph matching algorithm. Work carried out in two phases, offline phase and online phase. Offline phase grnertaes index over data graph G. Online phase retrieves set of subgraphs from data graph G which are similar to query graph Q. A cost function is introduced for checking similarity of query node with data graph node which efficiently reduces intermediate results by converting vertices into vector points and extracts similar subgraphs by calculating nearest distance of these vector points.

1. Nar Singh Deo, "Graph theory with applications to engineering and computer science".
2. J. R. Ullmann, "An algorithm for subgraph isomorphism," J. ACM, vol. 23, no. 1, pp. 31–42, 1976.
3. L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, "A (sub)graph isomorphism algorithm for matching large graphs," IEEE Trans. Pattern Anal. Mach. Intell. , vol. 26, no. 10, pp. 1367–1372, Oct. 2004.
4. H. Shang, Y. Zhang, X. Lin, and J. X. Yu, "Taming verification hardness: An efficient algorithm for testing subgraph isomorphism," Proc. VLDB Endowment, vol. 1, no. 1, pp. 364–375, 2008.
5. Y. Tian and J. M. Patel, "Tale: A tool for approximate large graph matching," in Proc. 24th Int. Conf. Data Eng. , 2008, pp. 963–972.
6. S. Zhang, S. Li, and J. Yang, "Gaddi: Distance index based subgraph matching in biological networks," in Proc. 12th Int. Conf. Extending Database Technol. : Adv. Database Technol. , 2009, pp. 192–203.
7. L. Zou, L. Chen, and M. T. Ozsu, "Distance-join: Pattern match query in a large graph database," Proc. VLDB Endowment, vol. 2, no. 1, pp. 886–897, 2009.
8. P. Zhao and J. Han, "On graph query optimization in large networks," Proc. VLDB Endowment, vol. 3, nos. 1/2, pp. 340–351, 2010.
9. H. He and A. K. Singh, "Graphs-at-a-time: Query language and access methods for graph databases," in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2008, pp. 405–418.
10. Liang Hong, Lei Zou, Xiang Lian and Philip S. Yu, "Subgraph Matching with Set Similarity in a Large Graph Database," in Proc. IEEE VOL. 27, NO. 9, pp, 2507–2521,2015.

Graph Database Offline Phase Online Phase Subgraph Matching