Research On Index Construction Method In Subgraph Isomorphism

Given a query graph q and a data graph g,the subgraph isomorphism search finds all occurrences of q in g.Subgraph isomorphism search is actively used in many applications,such as protein interaction analysis,chemical compound search,graph classification,scene analysis and computer-aided design of electronic circuits.In theory,subgraph isomorphism search belongs to NP-Complete problem,but extensive works have been done in trying to solve it in reasonable time for real datasets.In order to carry out efficient subgraph isomorphism query,we need to construct the corresponding index for the data graph,however,the existing indexing method is inefficient and poorly scalable.The paper is the research of the index construction of data graph in subgraph isomorphism search,and the research contents are organized as follows.Firstly,by thorough analysis for the existing methods of indexing the data graph in subgraph isomorphism query,and find the reason for the low efficiency and poor scalability is as follows:(1)When searching for the equivalent node they use the step-by-step method,which exists a redundant calculation and result in low efficiency;(2)In the indexing process,the intermediate result data is large,resulting in poor scalability.Secondly,we propose the idea of ordering and verifying the equivalent nodes,and design the corresponding algorithm gIndex BasedSV to improve the efficiency of the equivalent node query.The gIndex BasedSV algorithm groups the nodes according to the label,and finds the nodes with the equivalence relation in the group.For the nodes that do not have the equivalence relation,the equivalence relation of the membership is found by means of verification,which reduces the repeated calculation of nodes and improves the efficiency of index construction.Thirdly,we propose the idea of twice ordering the equivalent nodes,and then design the corresponding algorithm gIndexBasedTS to further enhance the efficiency and expansibility of index construction.Based on the equivalence definition of nodes,gIndex BasedTS algorithm expresses the equivalent nodes with two kinds of neighbor information.And the spatial complexity of the algorithm is reduced to linear.With two sorties,the gIndexBasedTS algorithm avoids the high cost of the gIndexBasedTS algorithm in the verification phase,further enhancing the efficiency of indexing.At last,based on the datasets of different sizes,the efficiency and expansibility of the algorithms proposed in this paper are verified by experiments.