基于拓扑序列的DAG子图包含查询算法研究

• 作者: 吕建华 奚业雷 张柏礼
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 子图包含查询 有向无环图 拓扑序列 子图同构 图索引
• 年，卷（期）: 2011,（z2）
• 所属期刊栏目: Web与图数据
• 页码范围: 721-727
• 分类号: TP311.13
• 字数: 5660字
• 语种: 中文

摘要

图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,首先根据图中节点的偏序关系将有向图分层拓扑为一个序列,然后利用序列间的匹配关系过滤出候选结果集,最后通过子图同构检测验证得到最终结果集.相关性能测试表明,该算法无需构造复杂的索引结构,便于图数据库的动态维护,在有向无环图在线查询性能上表现出色.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张柏礼	东南大学计算机科学与工程学院	32	326	9.0	17.0
2	吕建华	东南大学计算机科学与工程学院	20	141	7.0	11.0
3	奚业雷	东南大学计算机科学与工程学院	1	4	1.0	1.0