Research On Graph Similarity Queries With Edit Distance Constrains

With the rapid development of modern information technology, graphs are widely used to model a variety of complex structured data such as social network, biology, semantic networks and pattern recognization. The problem of graph queries is one of the hot issues in graph management database. Currently, researches on isseues include subgraph queries and graph similarity queries. This paper studies the graph similarity queries with eidt distance constraints.First, by conducting an analysis of the existing algorithms, we found the problems of inefficient filtration efficiency and repeating treatment matching nodes.Secondly, for the problem of low efficiency filtering in existing methods in the presence of the filter stage, we proposed the degree filtering by calculating the minimum number of edges editing operation between the corresponding nodes of matching mapping. Then combined with dynamic partitioning the unmatching partition, we develop an algorithm Pars_Degree to filter the graphs that without matching partition and reduce the size of the candidate set to be verified.Thirdly, existing graph similarity queries methods focus on how to reduce the number of the candidates. But, how to quickly verify the similarity between candidate and query graph is not an easy task. For the problem of repeating treatment matching nodes in the validation phase of Pars_Degree algorithm, we proposed an improved A* algorithm which start from the matching partition with a best mapping sequence to extend the candidate graphs by sharing the computing of matching nodes in the filtering stage. Thus we can speed up the verification time and improv query efficiency.Finally, we conduct experiments using AIDS dataset by compare the query time of getting the query answers between different algorithms. It demonstrates that the algorithm proposed in this paper is efficiency and scalability.