| Subgraph query is that given a graph database and a query, retrieve all graphs whichcontain the query as subgraph(s) in the graph database. At present, subgraph query oftenuse the filter-and-verification framework to processing the query. In the filtering phase,features are selected as index and construct index structure, effective pruning rules areused to get the candidate set; In verification phase, we perform subgraph isomorphismbetween query and each graph in graph database to obtain the final result set. But a mainproblem of subgraph query is subgraph isomorphism that is a NP-Complete problem. Thepurpose of filter-and-verification framework is that reduce the number of subgraphisomorphism as much as possible, but the effectiveness of this method depends on thequality of selected features, index structure and the filtering algorithm. In order to solvethese problems, this paper provides an efficient subgraph query algorithm.Firstly, an effective feature index model is proposed that is feature tree index strategyin this paper. Selected feature should be found frequently, So frequent trees are selected asindex features, but a lot of redundancy trees exist in selected frequent tree sets, In order toremove the redundant frequent trees and reduce the feature size, the concept ofdiscriminative tree is defined, then the pruning power of the frequent trees are computedto select the discriminative and frequent trees as index.Secondly, an effective encoding method is proposed to filtering out the graphs thatare not possible in the results. First encode each vertex based on its local structures, andthen encode the structure of the whole tree, changing the comparison between thestructures into the comparison between the numerical sequences. These codes are insertedinto a prefix tree, two pruning rules are proposed to filtering the database, then get thecandidate set.Finally, we use two datasets to verify the correctness, efficient and runtime of thealgorithm in this paper. |
PDF Full Text Request