Research On Approximate Matching Method Of Pattern Graph With Regular Expressions

With the rapid development of the Internet,huge amounts of data appears in people’s daily life,and there may be a close relationship between these data.How to quickly and accurately find the content that meets the demand from the data modeled by the graph,that is,the data graph,is one of the hot topics in today’s research.Among others,these requirements can also be modeled with a graph,commonly referred to as a pattern graph.Graph pattern matching refers to the problem of finding all matches in a data graph for a given pattern graph.Graph simulation and subgraph isomorphism are two approaches mostly used to solve GPM problems.Compared with subgraph isomorphism,graph simulation has more capacity to capture more useful information due to its flexibility.Moreover,it can be solved in polynomial time.There are a large number of variants of graph simulation were proposed.Among them,Fan et al.added regular expressions of a certain form as the specifications to edges in pattern graphs,they have proved that the increased expressive power does not come with extra complexity.However,in real world graphs,because of data noise or errors arising from data collection,there exist some nodes approximately simulate the node in a pattern graph.By traditional graph simulation and its variants,these nodes will be ignored,which lead to a few potential results being missed.Therefore,to alleviate the aforementioned problem,in this paper,we extend the exact matching between data graphs and pattern graphs with regular expressions to an approximate perspective by combining the idea of formal verification.The main work is as follows:1、We extend the exact matching between data graphs and pattern graphs with regular expressions to an approximate perspective by using the relevant background knowledge of metrics.After that,the properties of the defined approximate graph simulation and approximate matching relations between data graphs and pattern graphs with regular expressions are discussed.Finally,we give two fixed point characterization methods to the approximate graph simulation.2、In order to use logic to characterization the approximate graph simulation and the approximate matching between data graphs and pattern graphs with regular expressions,we extend the classical Hennessy-Milner logic.After giving the syntax and semantic of the extended logic,we will introduce the logical characterization of the approximate graph simulation.Finally,the the approximate matching between data graphs and pattern graphs with regular expressions are characterized from a logical point of view.