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

DAG decomposition based algorithm for graph similarity containment query

作　　者：李先通[1] 李建中[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《哈尔滨工业大学学报》2009年第6期113-117,共5页Journal of Harbin Institute of Technology

基　　金：国家自然科学基金资助项目(60773063)

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

关 键 词：图查询 图挖掘 近似包含 

分 类 号：TP311.132[自动化与计算机技术—计算机软件与理论]