Research On Method Of Subgraph Query And Match Based On K Tolerance

Graph is a common data structure in computer science,relationships between entities in life are intricate and closely contacted with each other.So graph is widely applied in data modeling,and also played a more and more important role in matching complicated relationships between datas.How to effectively query and matching graph has become a hotspot of research in recent years. The subgraph matching methods already introduced almost filtered their nodes which were not satisfied with the matching conditions, and then matched their edges and graph. These were known as methods based on nodes, because they only used nodes’information to filter out elements that didn’t satisfy the matching conditions. However, the edges of graph which cover large amount of information were not effectively used.Approximate subgraph is refered to subgraphs which don’t lost any node of the query graph, but only miss a certain number of edges, the threshold of missing edges’ amount is called degree K of tolerance. Noise’factors make the edges’information missing of graph become common, even in the case of lacking of edges, we also need to search the query graph’ approximate matching subgraphs for future’s studies and analysis.Therefore, this paper presents graph’s approximate subgraph matching method based on edge. First of all,we introduce the index of edges’labels in graph, which can achieve efficient filtering and query in graph. Making full use of the index’s information of edges can not only filter out the unqualified (mismatched) nodes and edges in the retrieval stage, but also can avoid unnecessary nodes and edges’ connectivity qualifying in matching stage, thereby reduce the algorithm’s redundant matching step. Secondly, preprocess the given query graph, generate querying edges’ sequence of approximate subgraph query and exact subgraph query for matching. Finally, introduce the data structure of improved bit string vector, it can fulfill the subguraphs’ matching verification and connectivity detection, thus improve the subgraphs’matching efficiency, and reduce redundant subgraphs’maching steps.In real data sets and synthetic data sets, compare the method of KTSM presented in this paper with the existing methods of SAPPER and GADDI, we change four parameters one time respectively and analyze the experimental results, thus verify that the method of this paper has subgraph matching capability on both synthetic datasets and real network datasets, and greatly improve the efficiency of subgraph matching and querying.