关键词: 图近似查询, DAG图, 最小生成树

Abstract:

The graph approximate query of graph data can get result sets similar to the query graph.It’s been more widely applied in many areas than accurate query.To obtain complete and reliable results,we propose an algorithm based on graph decomposition.This algorithm decomposes the query graph and the graph data according to the graph structure,and makes an index based on DAG.Utilizing the minimum spanning tree set of the query graph,we get the spanning tree set with a threshold;and we use graph standard codes for quick query and get approximate results as many as possible.The experimental results show that the algorithm can effectively get the approximate results and improve the query speed.

Key words: graph approximate search;DAG graph;minimum spanning tree