基于DAG解构的图近似包含查询算法

为解决图集近似包含查询,提出一种基于图解构的GCSS算法.该算法通过对图集中的目标图进行解构,得到图集中子图分布情况,并利用该子图分布建立索引.在此索引基础上的查询算法对图集进行近似包含查询,不但可以避免确定候选集的过程中产生过多子图同构测试,而且形成较小候选集,提高验证阶段效率.实验结果表明,GCSS算法能高效完成近似包含查询任务,得到图集中被查询图近似包含的正确结果.

DAG decomposition based algorithm for graph similarity containment query

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.