Research Based On DFSTree Neighborhood Index On Large Graph Matching Algorighm

Graphic structure models are often used in the fields of Internet,biology,computer vision,and chemistry to describe complex objects and the relationship between them.Graph search in the field of graph computing research plays an important task in a variety of applications and falls under two scenarios: subgraph querying and subgraph matching: where the subgraph query is in the graph database to find all the matching query matching of the hypergraph set and return;subgraph matching is from the graph database to find all with the query isomorphic subgraph and return.No matter which type : graph query or matching,subgraph isomorphism algorithm should be used to judge whether the candidate graphs are really isomorphism to the given query graph before the results return.It is well known that the subgraph isomorphism problem is a NP complete problem,and the subgraph isomorphism can be implemented by search pruning or fast heuristic algorithm.Search based subgraph isomorphism algorithm in the time consuming expensive,so it is impractical to scan all the graphs in the database and judge the isomorphic relationship.In order to solve this problem,the researchers puts forward and applies the technology of graph indexing,which is used to construct the index of the graph structure to filter out the graphs that do not satisfy the matching conditions.In this way,we need to perform the same size reduction as the size of the graph,so as to improve the efficiency of the algorithm.Based on graph index algorithm,researchers have proposed the most commonly used filtering-verification algorithm for graph matching query.Based on the traditional mining and non mining graph index construction algorithm is limited to the graph size,when the graph size becomes very large it lose its usage.In this paper,we propose a new tree-based approach for improving subgraph searching performance.The research algorithms used in this paper are the traditional graph filtering-verification algorithm based on query search framework,the difference is the graph indexing algorithm used here is generated by neighborhood vertices around the given vertex by depth first search method to build tree structure.The DFSTree tree height is specified by the given neighborhood radius.In the graph matching stage we designed DFSTree to restore the structure through the algorithm based on tree structure,through the method of the candidate vertex set for the graph reduction,and the reduction was generated as a candidate graph atlas query graph.Our work has the following contributions: First,candidate vertices are identified.Then,a joining processing by comparing relationships of candidate vertices in the large graph to the original query graph is used to further verify these candidates.Both vertex pruning and query reconstructing abilities of different structural patterns such as neighborhood trees are selected to be the most feasible candidates.To reduce the size of candidate set,we propose a new cost-effective graph indexing techinique,DFSTree,which makes the use of the trees around the given vertex neighborhood for pruning proposes.Canonical unordered trees are leveraged,and the string comparison technique is used to accerlerate the subtree containment process.To address the second step,we propose an efficient searching method for joining the neighborhood trees and reconstructing the original query graph.We conduct the experiments by using both real and random synthetic graph datasets.By comparing our tree-based indexing method DFSTree with state-of-the-art path-based indexing methods.The experiments data results show that even though indexing building time and space consumption our tree based indexing method is slightly inferior to path-based indexing method.But our indexing method outperforms SPath indexing methods in terms of candidate filtering and graph matching performance.