An Improved Method of Subgraphs Extraction in a Large Graph Database in a Distributed System by considering both Graph Topology and Set Similarity

Ritu Yadav, Samarth Varshney

Abstract


Since many real applications such as web connectivity, social networks, and so on, are emerging now-a-days, thus graph databases have been widely used as important tools to model and query complex graph data wherein each vertex(node) in a graph usually contains information, which can be modelled by a set of tokens or elements. The method for subgraphs extraction by considering set similarity query over a large graph database has already been proposed, which retrieves subgraphs that are structurally isomorphic to the query graph, and meanwhile satisfy the condition of vertex pair matching with the (dynamic/fixed) weighted set similarity in a centralized system. This paper explains the efficient implementation of subgraphs extraction in a large graph database in a distributed environment by considering both vertex set similarity and graph topology which offers a better price/performance ratio and increases availability using redundancy when parts of a system fail than centralized systems in case of a large dataset (i.e., a graph with millions/billions of nodes wherein each node contains some information) by performing parallel processing.

References


Z. Sun, H. Wang, H. Wang, B. Shao, and J. Li, “Efficient subgraph matching on billion node graphs,” Proc. VLDB Endowment, vol. 5, no. 9, pp. 788–799, 2012.

P. Zhao and J. Han, “On graph query optimization in large networks,” Proc. VLDB Endowment, vol. 3, nos. 1/2, pp. 340–351, 2010.

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.

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.

H. He and A. K. Singh, “Closure-tree: An index structure for graph queries,” in Proc. 222nd Int. Conf. Data Eng., 2006, p. 38.

W.-S. Han, J. Lee, and J.-H. Lee, “Turboiso: Towards ultrafast and robust subgraph isomorphism search in large graph databases,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2013, pp. 337–348.

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.

J. R. Ullmann, “An algorithm for subgraph isomorphism,” J. ACM, vol. 23, no. 1, pp. 31–42, 1976.

S. Ma, Y. Cao, W. Fan, J. Huai, and T. Wo, “Capturing topology in graph pattern matching,” Proc. VLDB Endowments, vol. 5, no. 4, pp. 310–321, 2012.

A. Khan, Y. Wu, C. C. Aggarwal, and X. Yan, “Nema: Fast graph search with label similarity,” in Proc. VLDB Endowment, vol. 6, no. 3, pp. 181–192, 2013.

Liang Hong, Member, IEEE, Lei Zou, Member, IEEE, Xiang Lian, Member, IEEE, and Philip S. Yu, Fellow, IEEE , " Subgraph Matching with Set Similarity in a Large Graph Database " , IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 27, NO. 9, SEPTEMBER 2015




DOI: https://doi.org/10.23956/ijarcsse/V7I6/0233

Refbacks

  • There are currently no refbacks.


Bookmark and Share


© International Journals of Advanced Research in Computer Science and Software Engineering (IJARCSSE)| All Rights Reserved | Powered by Advance Academic Publisher.