CFP last date
20 June 2024
Reseach Article

Subgraph Matching Algorithm for Graph Database

Published on March 2017 by Maninder Rajput, Snehal Kamalapur
Emerging Trends in Computing
Foundation of Computer Science USA
ETC2016 - Number 2
March 2017
Authors: Maninder Rajput, Snehal Kamalapur

Maninder Rajput, Snehal Kamalapur . Subgraph Matching Algorithm for Graph Database. Emerging Trends in Computing. ETC2016, 2 (March 2017), 15-19.

author = { Maninder Rajput, Snehal Kamalapur },
title = { Subgraph Matching Algorithm for Graph Database },
journal = { Emerging Trends in Computing },
issue_date = { March 2017 },
volume = { ETC2016 },
number = { 2 },
month = { March },
year = { 2017 },
issn = 0975-8887,
pages = { 15-19 },
numpages = 5,
url = { /proceedings/etc2016/number2/27309-6262/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
%0 Proceeding Article
%1 Emerging Trends in Computing
%A Maninder Rajput
%A Snehal Kamalapur
%T Subgraph Matching Algorithm for Graph Database
%J Emerging Trends in Computing
%@ 0975-8887
%V ETC2016
%N 2
%P 15-19
%D 2017
%I International Journal of Computer Applications

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.
Index Terms

Computer Science
Information Sciences


Graph Database Offline Phase Online Phase Subgraph Matching