The Research On Subgraph Matching Algorithm In Large Graph Databases

Subgraph matching is a principal question in graph theory.The definition of subgraph matching is giving a query graph, finding all subgraphs in large graph databases which have the same structure and node label with the query graph.In practice, we are always concerned with the subgraphs which get a higher score.So we propose the thought about Top-K subgraph matching. It`s similiar to subgraph matching, but in Top-k subgraph matching, it will sort the final result and show us K subgraphs which has the higher score compared with others. So Top-K subgraph matching is more pertinent. The paper is the research of the Top-K subgraph matching search in large graph databases, and the research contents are as follows.Firstly we use filtering-matching method to find the subgraph matching. The efficiency of the algorithm is concerned with the filter effect and the rate of match section. Compared with the exist method, we find that in filter section has these problems:(1) the equal vertexes may be enumerated many times;(2) the inefficiency of pruning method based on the structure of path;(3) choose the wrong starting point.In match section we find that there are too many redundancy matchings.Secondly, in filter section, we propose a PFilter algrothim. We set a compress method to compress equal vertexes to reduce the enumeration number of equal vertexes. We use the structure of each vertex as the pruning method to make the pruning method efficiency. We propose a matching order: choosing the query vertex which has the fewest candidate nodes as the starting point to reduce the number of enumeration.Thirdly, in match section, we propose a PGet Score algrothim. We use the RWM(ranking while matching) method to decrease the time spend on checking results and reduce the redundancy matchings.Finally, the experiment shows that our method is much more efficient than existing methods according to the processing time, the efficiency of compression and so on.