Research On Graph Search Problem Based On Edit Distance

Graphic similarity information,as the key value information that people want to explore,has always been concerned by scholars.However,the metric of graph edit distance(GED),which is used to mine similar information of graphs,has been consistently adopted by people because of its rich semantic information.However,the calculation of edit distance of graphs has been proved to be NP-hard problem,so the graph search problem based on edit distance has been favored by scholars in recent years.In the current research work,because the proposed graph search framework of "filter + verification" is only limited to graph search with a single threshold,it cannot be effectively extended to search for the top-k similar results,and the calculation is still very slow in the verification stage,so this paper divided it into three problems to carry out research.The main research achievements and contributions are as follows:The problem of finding k result graphs which are most similar to the query graph in the graph database is studied.Firstly,the offline index building algorithm HII is designed.Its main function is to find the similar graph in each layer.Secondly,the online query algorithm TGSS is used to traverse the partition-based inverted index.Finally,the fast response time and scalability of the proposed algorithm are proved by experiments.Research on the edit distance calculation during the validation stage in graph search with A* algorithm.Firstly,two problems ignored by A* algorithm in the validation stage are proposed: the preprocessing of map sequence and the priority of maps at the same cost in the priority queue;Secondly,the Determine VO and Update Q algorithm are designed to solve the above problems.At the same time,on the basis of previous work,Return LB is used to improve the tightness of the mapping lower bound.Finally,the time performance and scalability performance of the proposed algorithm are verified in experiments.Research on the candidate set reduction method in "filter + validation" framework.Firstly,by analyzing the problem of large candidate set and verification set after filtering by traditional graph similarity search method,a method of reducing candidate set is introduced.Secondly,we use Refined C and Construct Idx algorithms for offline index and online search respectively,and put forward optimization algorithms for the shortcomings of online and offline stages respectively.Finally,the effectiveness of the optimized algorithm is verified.