Research On Algorithms For Subgraph Query Based On Single Neighborhood

As we all know, the complexity of the subgraph isomorphism query is the NP complete problem. In order to improve the query performance, many of the subgraph isomorphism query method is proposed. Most of the existing work is based on the framework of the filtering and verification. Specifically, we build an index in the offline phase and according to the index, the effective filtering algorithm is used to reduce the candidate query space of the vertex in the operation stage. Finally, the subgraph isomorphism algorithm is used to find all matches of the graph. Experiments show that these valid methods are not feasible and efficient enough. In order to realize the fast subgraph isomorphism query, this paper proposes a subgraph query algorithm based on single neighborhood.Firstly, In order to improve the query speed, this paper proposes an index method based on single neighborhood. The global label index is constructed. The vertices of the graph data are classified according to the labels in order to query label candidates of the query vertices and total candidate numbers. The vertex single neighborhood list is created in order to use vertex single neighborhood information as a pruning condition and reduce the numbers of false positive candidates of the vertexes. we find that the query graph matches are only relevant to certain areas of the data graph and the candidates of the query vertices are only relevant to finite vertexes in the candidate regions instead of the candidate vertexes in the data region. Therefore, this paper proposes the initial vertex method how to find.Secondly, in order to avoid the invalid connection detection problem in the sub graph verification phase, a query algorithm based on the single neighborhood is proposed.Firstly the paper gives the single neighborhood matching rules and matching order. Next according to the characteristics of query algorithm, the paper gives the candidate vertex storage structure. Then in order to avoid having the unnecessary recursive in the query process, the paper gives the no candidate vertex matching concept. Besides, in order to avoid exploring candidate regions repeatly in the query process, the paper gives the overlapping candidate region query strategy. The vertexes whose degrees are one have itsown unique characteristics in the single neighborhood query. For the problem, the algorithm is further optimized.Finally, the algorithm of the paper and the algorithm SPath in the real data sets are verified and compare the performance from the aspects of index creation time and running time.