基于容忍度K的子图查询匹配方法研究

发布时间：2017-09-08 08:39

  本文关键词：基于容忍度K的子图查询匹配方法研究

  更多相关文章： 图 近似子图 容忍度 索引 子图匹配

【摘要】：图是计算机科学中常见的数据结构,生活中实体与实体之间的关系错综复杂、联系紧密,因此图在众多复杂数据建模中广泛应用,在匹配复杂数据关系的过程中也扮演着越来越重要的角色,如何对图进行有效查询和匹配成为近些年的研究热点。在已提出的子图匹配方法中,首先过滤掉不满足匹配条件的节点,然后再进行边和图的匹配,这称为基于节点的方法。然而这种方法仅仅使用节点信息过滤掉不满足匹配条件的元素,图的边涵盖大量的信息却没有效利用。近似子图是指不缺失查询图的任何节点,而只丢失一定数量的边,而边丢失的数量处在一定范围内,这个阈值称为容忍度K。噪声因素使图的边信息丢失变得常见,即便在边缺失的情形下,也要找到查询图的近似匹配子图以备研究和分析。因此,本文提出了图的基于边的近似子图匹配方法。首先,提出图的边标签索引,它能实现对图的高效过滤和查询。充分利用边的索引信息,在查询检索阶段不仅能过滤掉不合格(不匹配)的节点和边,也避免了匹配阶段进行不必要的节点、边连通性检测,从而减少了算法的冗余匹配步骤。其次,对给定的查询图进行预处理,生成查询图的近似子图查询边序和精确子图查询边序进行查询和匹配。最后,引入改进的位串向量数据结构,对被查询图的子图进行子图匹配验证和连通性检测,从而提高图的子图匹配效率,减少冗余的子图匹配步骤。在真实数据集和合成数据集上,将本文提出的KTSM方法和现有的GADDI、 SAPPER等方法进行对比,在分别变化四种参数时的实验结果进行比较和分析,验证了本文提出的子图匹配方法在现实图网络和合成数据集上,都具有较好的查询匹配能力,子图匹配的效率得到了极大的提高。
【关键词】：图 近似子图 容忍度 索引 子图匹配
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要4-5
• abstract5-11
• 第1章 引言11-17
• 1.1 研究背景11-12
• 1.2 研究现状12-14
• 1.3 研究内容14-15
• 1.4 本文组织结构15-17
• 第2章 图查询问题概述17-23
• 2.1 图存储17-18
• 2.2 图查询18-19
• 2.3 查询匹配方法19-22
• 2.3.1 基于结构的方法19-20
• 2.3.2 基于特征的方法20-21
• 2.3.3 基于节点的方法21-22
• 2.4 本章小结22-23
• 第3章 图索引及查询图预处理23-37
• 3.1 图索引23-26
• 3.1.1 标签图23-24
• 3.1.2 索引24-26
• 3.2 子图查询26-30
• 3.2.1 精确子图与近似子图27-28
• 3.2.2 容忍度K28-29
• 3.2.3 单图和多图29-30
• 3.3 查询图预处理30-36
• 3.3.1 查询图ID31
• 3.3.2 近似子图查询边序31-34
• 3.3.3 精确子图查询边序34-36
• 3.4 本章小结36-37
• 第4章 查询图容忍度K的子图匹配判定37-53
• 4.1 不等式属性37-38
• 4.2 位串向量38-42
• 4.2.1 传统Hash38-39
• 4.2.2 改进Hash39-40
• 4.2.3 位串置位40-41
• 4.2.4 位串错误率41-42
• 4.3 匹配判定42-43
• 4.4 子图匹配43-52
• 4.4.1 近似子图匹配43-47
• 4.4.2 精确子图匹配47-52
• 4.5 本章小结52-53
• 第5章 实验及分析53-61
• 5.1 实验环境介绍53
• 5.2 实验数据集53-54
• 5.2.1 真实数据集54
• 5.2.2 合成数据集54
• 5.3 性能评估指标54-55
• 5.4 实验结果分析55-60
• 5.4.1 真实数据集对比55-57
• 5.4.2 合成数据集对比57-60
• 5.5 本章小结60-61
• 第6章 总结与展望61-63
• 6.1 总结61
• 6.2 展望61-63
• 致谢63-65
• 参考文献65-69
• 攻读学位期间发表的学术论文及参加科研情况69

【参考文献】

中国期刊全文数据库 前2条

1 张硕;高宏;李建中;邹兆年;;不确定图数据库中高效查询处理[J];计算机学报;2009年10期

2 周傲英;金澈清;王国仁;李建中;;不确定性数据管理技术研究综述[J];计算机学报;2009年01期

，

本文编号：813020