Research On Subgraph Search Technology In Graph Database

As a common data structure,graph is widely used to model and present viriouscomplex structured data In recent years,researchers all over the world focusattention on management of the accumulated graph data(graph database)Subgraphsearch is a valuable query type,it mainly contains exact subgraph search and similarsubgraph search Specifically,exact subgraph search returns graph set{g∈D |ョg∈g,s．tg and q are isomorphic graphs)；similar subgraph search returnsgraph sets{g∈D|ョg∈g,s．tg and q are similargraphs) In this paper,vcepropose effective methods to solve both query types described aboveFor exact subgraph search,the paper applies a schema using filtering andverification,feature is a special frequent subgraph mined from graph database,andfiltrator is a index tree organized from features Because many features shares acommon induced subgraph,so the induced subgraph only maps into query graphonce when testing subgraph isomorphism in filtering phase,filtering can completeefficiently Considering that the cost of extracting features is large,vce design aefficient algorithm to extract features,and the features have good filteringeffectiveness Both theoretical analysis and experiment show that our method isbetter than the existing methodsFor similar subgraph search,two graphs are similar if they have the sametopology and the edit distance between them is lower than some threshold Theexisting methods mainly apply filtering verification framework,in this framework,researchers mainly focus on constructing index to increase filtering effectiveness,butfew of them consider a efficient verification method Specifically,when verificatingwhether q is a similar subgraph of g,these methods must enumerate subgraphs gof g until they find a subgraph g whose distance to query is lower than somethreshold Enumerating subgraphs in g costs too large The method proposed in thispaper does not need enumerating subgraphs,it just transform the simiar subgraphsearch problem to computing graph edit distmace from g to q. Through analyzingthe characteristic of the problem,vce design a heuristic algorithm to compute editdistance from g to q,which can increase the efficiency of verification In addition,considering the NP hardness of compute graph edit distmace,vce also design amethod to compute the lower bound of edit distance in polynomial time We can filter some false results using this lower bound A lot of experiments on real andsynthetic data sets show that our method outperforms the existing methods...