DAG decomposition based algorithm for graph similarity containment query
Jianzhong Li · Ha'erbin gongye daxue xuebao · 2009
An algorithm based on DAG decomposition,namely GCSS,is proposed to implement the problem of graph similarity containment query. The index is built on the subgraph distribution drawn from the decomposition of target graph in graph dataset. Deployed on such index structure,the algorithm can not only avoid extra subgraph isomorphism tests in finding out candidate answer set,but also output a smaller set to increase the efficiency of verification stage. Experimental result shows that GCSS performs an efficient graph similarity containment query and gets the right results.