Study On Indexing For Subgraph Similarity Matching Using Frequent Subgraphs

As a new branch of Combinatirics mathematics, graph theory began at the famous discussion on Kongsberg Bridges Problem, it’s the study of graphs. In recent years, stimulated by the development of computer science, graph theory is also rapidly developing, the range of its applications is continually expand, more and more datas are modeled by graph, such as chemical compounds, protein-protein interaction networks, etc. With the amount of these graph datas is continually increasing, how to effectively manage and mining vast amounts of graph datas is the core issues of graph database.In recent years, similarity search on graph database has been pay more and more attention, as the complexity of graph datas’structure is, how to find the answers approximately satisfying the requirement has been a great challenge. In this thesis we propose an efficient indexing mechanism for similarity search by analysing topological structures and frequent patterns of graph datas. The main contribution of this paper includes:Firstly, a new measurement of similarity between graphs is proposed. In this paper, we begin from the definition of graph’s edit distance, and study the topological relationship of graphs, and give the expression of the similarity between graphs. The expression provides a theoretical proof of the similarity search algorithm proposed by this thesis.Secondly, we proposed a new indexing method. Inverted Frequent subgraph Index, based on frequent subgraphs, to avoid the shortcoming of the prior work that focus on the matching between two graphs. The performace of this method is more better than the traditional sequential searching on the database.Thirdly, observing that frequent subgraph properties can accelerate the process of local frequent subgraph isomorphism. a new indexing method, Layered Inverted Frequent subgraph Index (LIF-lndex), has been proposed. It organizes indexed terms by using a layered structure. Experiments showed that the method accelerates the process of local frequent subgraph search.Finally, we introduce the filter principle to Layered Inverted Frequent subgraph Index (LIF-Index), design an efficient algorithm of similarity search, and compare it with another indexing method, gIndex, in the experiment.Experiments showed that the techniques this paper proposes have good performance.