支持动态图数据的子图查询方法

• 作者: 李晓华 杨晓春 王斌 王楠
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 子图查询 动态图数据 拓扑序列 图索引
• 年，卷（期）: 2014,（2）
• 所属期刊栏目: 数据库技术
• 页码范围: 139-149
• 页数: 11页
• 分类号: TP311.1
• 字数: 8912字
• 语种: 中文

摘要

近年来，子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的，而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题，在动态图数据上子图查询问题就变得更加困难。针对上述问题，提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引，在序列中加入标号以便数据更新后对索引进行维护，再根据序列间的匹配关系过滤出候选集合，最后采用图同构算法验证候选集中的图，最终得到结果集合。该方法的索引构造简单且体积小，并且在图数据库更新后无需重构索引，不仅支持动态图数据上的子图查询，在静态图数据上也表现出良好的性能。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王楠	东北大学信息科学与工程学院	62	589	13.0	22.0
2	杨晓春	东北大学信息科学与工程学院	65	1090	16.0	32.0
3	王斌	东北大学信息科学与工程学院	101	945	14.0	28.0
4	李晓华	东北大学信息科学与工程学院	15	76	5.0	7.0