基于DAG解构的图近似包含查询算法
DAG decomposition based algorithm for graph similarity containment query作者机构:哈尔滨工业大学计算机科学与技术学院哈尔滨150001
出 版 物:《哈尔滨工业大学学报》 (Journal of Harbin Institute of Technology)
年 卷 期:2009年第41卷第6期
页 面:113-117页
核心收录:
学科分类:0810[工学-信息与通信工程] 12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0805[工学-材料科学与工程(可授工学、理学学位)] 0812[工学-计算机科学与技术(可授工学、理学学位)]
摘 要:为解决图集近似包含查询,提出一种基于图解构的GCSS算法.该算法通过对图集中的目标图进行解构,得到图集中子图分布情况,并利用该子图分布建立索引.在此索引基础上的查询算法对图集进行近似包含查询,不但可以避免确定候选集的过程中产生过多子图同构测试,而且形成较小候选集,提高验证阶段效率.实验结果表明,GCSS算法能高效完成近似包含查询任务,得到图集中被查询图近似包含的正确结果.