Approximate Query Algorithm Based on Graph Topological Relation
Shou Jian Yu, Xin Kun Zhang · 2018
With the rapid development of information technology and the Internet, data produced by people in daily life is becoming more and more huge and complex. Graph-Based Modeling of the complex data structure becomes more and more popular in recent years. Matching query is the basis of the entire graph database. In this case, approximate query algorithm of general graph has very high practical value. This paper aims to propose an approximate query algorithm based on topological relations of graphs. The approximate query algorithm analyzes the topological structure of the graph, and organizes different sizes of items we got to the DAG (Directed Acyclic Graph). Then we can extend it according to the minimum spanning tree produced by query graph. Finally we get the extended spanning tree which satisfies certain conditions. We can encode the standard spanning graph of the extended spanning tree, and then put it into the DAG graph to realize fast indexing and obtain candidate set of the query graph quickly, which can improve the efficiency of query.