Research And Implementation Of Graph Pattern Matching With Counting Quantifiers

As a way to enhance the expression,counting quantifiers adding to the pattern matching can be more accurate description of the objective world.By simply adding counting terms to the edge of the query graph,it is natural to express entire and existence,ratio and constant aggregation,and negative logic.This pattern matching,which inproves the ability of expression,has a wide range of directed application in social media marketing,knowledge discovery,and network security.The research on graph matching problem with quantifiers is still relatively span-new,and the problem generalizes and contains the traditional pattern matching problem.The traditional pattern matching problem only belongs to a special case of this paper.Therefore,the complexity of the graph matching problem in this paper is far complicated than the traditional pattern matching's.Whether or not containing the negative quantifier on the edge of the graph can divide the problem into two subproblems with two different degrees of complexity.The first kind of sub-problem pattern graph contains only positive counting quantifiers,and it s complexity can prove to be NP-Complete,and the upper and lower bounds of complexity under certain conditions are NP,and the complexity of the matching problem with the negative quantifiers is DP-Complete,and the upper and lower bounds of the complexity are DP,The complexity makes the cost time of solving the problem unacceptable using the brute force method.This article realized(1)solution to positive QGP problem,which is improved by calling subgraph isomorphic subroutine.In this paper,we prove that the matching time of the algorithm is great within 4 edges,the scale of the matching time grows exponentially.(2)The matching algorithm of the negative QGP problem,Inc QMatch,which avoids the high complexity of verifying the negative count quantifier directly.On the basis of the problem solved above,we construct two new query graph structures with the idea of set difference operation to get the final result set.By recording we can avoid the second query from the beginning to effectively reduce the running time,and through the multi-threaded way we achieve the matching of the problem in parallel,the experiment shows that when there is only one negative quantifier on the edges of graph Only The query time after query scale more than 4 shows an exponential growth using Inc QMatch.(3)Using the hash coding technique to encode the label and node label around the key vertiex,we can compress the surrounding structure information and encode the surrounding label type information into a string of binary strings by matching code,In this experiment,the use of 8+8 bit encoding,we can filter out 95% of the mismatch.Optimization efficiency is very obvious,and when the query map size is lower than 6,the operation time was less than 10 seconds.Optimization effect is very obvious.