International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 9, No. 4, 8 Apr. 2017
Cover page and Table of Contents: PDF (size: 640KB)
A Survey on Graph Queries Processing: Techniques and Methods
Full Text (PDF, 640KB), PP.48-56
Views: 0 Downloads: 0
Author(s)
Hamed Dinari
1,*
Index Terms
Graph Mining, data mining, graph database Indexing, graph query processing, pattern matching
Abstract
Graphs are widely used to model complicated structures and link them with each other. Some of such structures are XML documents, social networks, and computer networks. Information and model extraction from graph databases is a graph mining process. Efficient query search in graph databases, known as query processing, is one of the heated debates in the field of graph mining. One of the query processing techniques is sequential search over the whole dataset and isomorphism test on all sub-graphs in the database, which is not an optimal technique as to response time and storage. This problem brought in the issues of indexing graph databases to improve query processing performance. As the method implies, part of the database where the answer is expected to be found there is pruned and the number of needed isomorphism tests decreases. It might not be easy to compare the methods and techniques of graph query techniques as different techniques have different objectives. For instance, similarity search techniques reduce query time, while they cannot compete with exact matching techniques as to accuracy and vice versa. Input data volume might be also effective on query time as with immense datasets, similarity search techniques are more preferred than exact matching techniques. The present study is a survey of graph query processing techniques with emphasis on similarity search and exact matching.
Cite This Paper
Hamed Dinari, "A Survey on Graph Queries Processing: Techniques and Methods", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.4, pp. 48-56, 2017. DOI:10.5815/ijcnis.2017.04.06
Reference
[1]S. Zhang, M. Hu, and J. Yang, "TreePi: A Novel Graph Indexing Method," in IEEE 23rd International Conference on Data Engineering, Istanbul, 2007, pp. 966-975.
[2]J. Huan, W. Wang, D. Bandyopadhyay, J. Snoeyink, J. Prins,and A. Tropsha, "Mining Protein Family Specific Residue Packing Patterns from Protein Structure Graphs," in in Proceedings of the 8th Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2004, pp. 308-315.
[3]C.Borgelt, and Michael, R. Berthold, "Mining Molecular Fragments: Finding Relevant Substructures of Molecules," in International Conference on Data Mining (ICDM), 2002, pp. 51-58.
[4]Pizzuti, Clara. , "GA-Net: A genetic algorithm for community detection in social networks.," Parallel Problem Solving from Nature–PPSN, 2008; pp. 1081-1090.
[5]Misra, Sudip, Romil Barthwal, and Mohammad S. Obaidat, "Community detection in an integrated internet of things and social network architecture," in Global Communications Conference (GLOBECOM), IEE 2012; pp. 1647-1652.
[6]H.Dinari, H.Naderi, "A Survey of Frequent Subtrees and Subgraphs Mining Methods," International Journal of Computer Science and Business Informatics, Jun. 2014; vol. 14:1, pp. 39-57.
[7]B. T. Messmer, and H. Bunke, "A Decision Tree Approach to Graph and Subgraph Isomorphism Detection," Pattern Recognition, Dec. 1999; vol. 32, no. 12, pp. 1979-1998.
[8]S. Raghavan and H. Garcia-Molina, "Representing Web Graphs," in IEEE Inernationall Conference on Data Engineering , 2003, pp. 405-416.
[9]Wang, Haixun. Ed. Charu C. Aggarwal. , Managing and mining graph data, V. 40, Ed. New York, USA: Springer, 2010.
[10]S.Sakr, E.Pardede, Graph Data Management: Techniques and Applications. United States of America: Information Science Reference (an imprint of IGI Global), 2012.
[11]Johansson, "Graph Decomposition Using Node Labels," Doctoral Dissertation, Royal Institute of Technology, 2001.
[12]He, Huahai, and A.K. Singh, "Closure-tree: An index structure for graph queries," in 22nd International Conference on Data Engineering (ICDE), Atlanta, Georgia, 2006; pp. 38-50.
[13]Chen, Zhiyuan, et al, "Index structures for matching XML twigs using relational query processors," in Data & Knowledge Engineering, 2007; pp. 283-302.
[14]Tian, Yuanyuan, and J. M. Patel, "Tale: A tool for approximate large graph matching," in IEEE 24th International Conference on Data Engineering (ICDE), 2008; pp. 963-972.
[15]Wood, Peter T, "Query languages for graph databases," ACM SIGMOD Record ,2012; vol. 41, no. 1, pp. 50-60.
[16]M. P. Consens and A. O. Mendelzon, " Expressing structural hypertext queries in GraphLog," In ACM Hypertext,1989; pp. 269–292.
[17]F. Cruz, A. O. Mendelzon, and P. T. Wood, "A graphical query language supporting recursion," In SIGMOD, May 1987; pp. 323–330.
[18]R. H. G¨uting, " GraphDB: Modeling and querying graphs in databases," In VLDB, 1994; pp. 297–308.
[19]M. Gyssens, J. Paradaens, and D. V. Gucht, " A graph-oriented object database model," In PODS,1990; pp. 417–424.
[20]Doulkeridis, Christos, and Kjetil N?rv?g, "A survey of large-scale analytical query processing in MapReduce," The VLDB Journal, 2014; vol. 23, no. 3, pp. 355-380.
[21]Cheng, Jiefeng, and Jeffrey Xu Yu. , "A Survey of Relational Approaches for Graph Pattern Matching over Large Graphs," Techniques and Applications Graph Data Management, 2011; pp. 112-141.
[22]Fan, Wenfei, et al. , "Graph pattern matching: from intractable to polynomial time," " Proceedings of the VLDB Endowment, 2010; vol. 3, no. 1-2, pp. 264-275.
[23]Yan, Xifeng, et al. , "Feature-based similarity search in graph structures," ACM Transactions on Database systems (TODS), 2006; vol. 31, no. 4, pp. 1418-1453.
[24]Gallagher, Brian, "Matching structure and semantics: A survey on graph-based pattern matching," AAAI FS 6, 2006; pp. 45-53.
[25]Bhargavi, B., and K. P. Supreethi, "Graph pattern mining: A survey of issues and approaches," International Journal of Information Technology, 2012; pp. 401-407.
[26]Shasha, Dennis, Jason TL Wang, and Rosalba Giugno, "Algorithmics and applications of tree and graph searching," Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems.ACM, 2002.
[27]J. R. Ullmann, "An algorithm for subgraph isomorphism," ACM, 1976; pp. 31-42.
[28]M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness.," W. H. Freeman & Co., 1979.
[29]Giugno, Rosalba, and D.Shasha, "Graphgrep: A fast and universal method for querying graphs," in IEEE, 16th International Conference on Pattern Recognition, 2002; pp. 112-115.
[30]Jiang, Haoliang, et al, "Gstring: A novel approach for efficient search in graph databases," in 23rd International Conference on Data Engineering(ICDE) IEEE, 2007; pp. 566-575.
[31]Yan, Xifeng, S.Philip Yu, and J.Han. , "Graph indexing: a frequent structure-based approach," in ACM SIGMOD international conference on Management of data, 2004; pp. 335-346.
[32]Cheng, James, et al., "Fg-index: towards verification-free query processing on graph databases," in ACM - international conference on Management of data(SIGMOD), 2007; pp. 857-872.
[33]Williams, W.David , J.Huan, and W.Wang, "Graph database indexing using structured graph decomposition," in 23rd International Conference on Data Engineering(ICDE) IEEE, 2007; pp. 976-985.
[34]X. Yan, P. S. Yu, and J. Han, "Substructure similarity search in graph databases," in international conference on Management of data. ACM, 2005; pp. 766-777.
[35]James, C. A., D. Weininger, and J. Delany?, "Daylight Theory Manual. Daylight Chemical Information Systems," 2003.
[36]Yan, Xifeng, et al, "Searching substructures with superimposed distance," in 22nd International Conference on Data Engineering (ICDE). IEEE, 2006; pp. 88-88.
[37]Chung, Chin-Wan, Jun-Ki Min, and K. Shim?, "APEX: An adaptive path index for XML data," in SIGMOD international conference on Management of data, 2002; pp. 121-132.