高效子图匹配算法研究

发布时间：2017-04-08 16:14

  本文关键词：高效子图匹配算法研究，，由笔耕文化传播整理发布。

【摘要】：图作为一种数据结构能够简洁有力地刻画出普遍事物间的联系,因此基于图的数据挖掘与管理技术无论在学术研究还是工业应用上都享有重要的地位。这其中最基本的任务是如何在图数据集中找到给定的查询图,也就是子图匹配问题。对于正在蓬勃发展的图数据库,生物信息学和社会网络分析等领域而言,一个高效的子图匹配算法的重要性不言而喻。子图匹配的数学基础是图论中的经典问题子图同构,一个著名的NP问题。可想而知,设计高效的子图匹配算法面临着相当巨大大的挑战。目前,子图匹配算法的研究工作主要有两个问题。其一是针对一张边数较多的图如何进行有效的过滤,其二是如何选择顶点搜索顺序来加快子图同构搜索的速度。特别是后者是近年来子图匹配研究的焦点。针对上述情况,本文提出了一个多段图模型(MGSM)用于指导顶点搜索顺序的选择。根据这个模型得到优化搜索顺序的两个关键点：特征选择和代价(导出子图)估计。其中,第一个关键点与过滤技术紧密相关,以此出发可以对以往算法的过滤技术进行改进。针对第二个关键点,本文提出了一种称为伪树估计的的代价估计方法。基于上述工作,本文设计了一个精确子图匹配算法Tps(Three-Phase-Searching)。实验结果表明：Tps算法不仅具有显著的高效性,同时优化的顶点搜索顺序对图过滤过程和验证过程同样有效。另外,本文在对精确与非精确匹配两个领域的重要算法进行分析的基础上,提出了一个高效的候选集过滤算法HLMA。实验证明,该算法既能满足尽量缩小候选集的过滤要求,又能兼顾过滤的时间效率。本文所描述的工作具有一定的创新性。其中,在与目前公认的最快图匹配算法TurboISO所进行的对比实验中,Tps算法具有明显的执行效率优势。更重要的是Tps算法的效率优势来自于更合理的理论基础,即本文所提出的MSGM模型可以指出何为最优的顶点搜索顺序。由此导出的两大关键点可以从理论上解释目前若干主要算法的相似相异之处,从而得出与相关对比试验结果相一致的经验结论。在此基础上提出的伪树估计法跳出了前人算法的藩篱,是Tps算法优异性能的根基所在。总而言之,MSGM模型为子图搜索算法进一步的研究提供了一个蓝图,而Tps算法是该蓝图下的一个初步尝试。
【关键词】：子图匹配 子图同构搜索 图挖掘
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP311.13
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-15
• 1.1 研究背景及意义11-13
• 1.2 本文研究的主要内容13-14
• 1.3 论文的组织安排14-15
• 2 子图匹配理论基础与研究现状15-24
• 2.1 子图匹配问题概述15-16
• 2.2 图索引技术的研究进展16-19
• 2.2.1 图索引的发展历程16-17
• 2.2.2 基于子图特征的图索引技术的基本理论17-19
• 2.3 子图同构搜索算法的发展历程与理论基础19-20
• 2.4 子图匹配问题的最新进展和主要挑战20-21
• 2.5 非精确匹配问题21-22
• 2.5.1 非精确匹配的研究进展与基本问题21
• 2.5.2 非精确匹配目前的挑战与成果21-22
• 2.5.3 非精确匹配算法对本文研究的意义22
• 2.6 本章小结22-24
• 3 基于多段图模型的高效子图匹配算法24-45
• 3.1 问题提出24
• 3.2 预备知识24-30
• 3.2.1 邻域过滤25-26
• 3.2.2 r-l路径过滤26-28
• 3.2.3 Ullmann算法和顶点搜索顺序28-30
• 3.3 多段图模型MGSM30-32
• 3.3.1 es特征31-32
• 3.3.2 导出子图频率的估计方法32
• 3.4 子图搜索算法32-36
• 3.4.1 伪树估计法33-35
• 3.4.2 搜索顺序生成35-36
• 3.4.3 Tps算法36
• 3.5 过滤方法的改进36-39
• 3.5.1 索引37-38
• 3.5.2 构造生成树38-39
• 3.6 实验39-43
• 3.6.1 构造实验数据集39
• 3.6.2 过滤阶段效率对比39-40
• 3.6.3 验证阶段效率对比40-43
• 3.7 本章小结43-45
• 4 基于邻域标签的快速过滤算法45-60
• 4.1 问题提出45
• 4.2 预备知识45-47
• 4.2.1 标签传播和h-list46-47
• 4.3 分层顶点过滤47-50
• 4.3.1 路径向量比对48-49
• 4.3.2 Label向量比对49-50
• 4.3.3 顶点向量比对50
• 4.4 HLMA全局过滤算法50-53
• 4.4.1 候选集生成51-52
• 4.4.2 候选集过滤：匹配度计算52-53
• 4.5 实验结果与分析53-59
• 4.5.1 查询准确率53-54
• 4.5.2 有效性54-57
• 4.5.3 时间效率57-58
• 4.5.4 与路径层矩阵的比较58-59
• 4.6 本章小结59-60
• 5 结论与展望60-62
• 5.1 本文总结60
• 5.2 未来展望60-62
• 参考文献62-65
• 作者简历及攻读硕士学位期间取得的研究成果65-67
• 学位论文数据集67

【相似文献】

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

1 张彩云;康亚男;成汝震;;基于内容的发布/订阅模型中高效的匹配算法[J];河北师范大学学报(自然科学版);2009年04期

2 赵力;周桑漪;;有关语音识别的几种模式快速匹配算法[J];苏州大学学报(自然科学);1991年03期

3 陈昊;李琼;赵绍东;;一种新的快速地磁匹配算法[J];传感器与微系统;2011年12期

4 李峰,周源华;基于内容的匹配算法[J];红外与毫米波学报;2000年01期

5 童余德;边少锋;蒋东方;向才炳;;一种新的基于局部重力图逼近的组合匹配算法[J];地球物理学报;2012年09期

6 谭志国;孙即祥;滕书华;;基于KL变换的点匹配[J];自然科学进展;2007年07期

7 章思亮;臧德彦;;基于转向角函数的形状匹配算法[J];科技广场;2009年01期

8 陈志楚;;一种基于k邻域算法的指纹匹配算法研究[J];赤峰学院学报(自然科学版);2012年19期

9 鲍文霞;梁栋;唐俊;;一种基于谱相关性的概率松弛匹配算法[J];光学学报;2010年03期

10 颜普;梁栋;王葵;;一种基于圈基的谱匹配算法[J];安徽大学学报(自然科学版);2012年05期

中国重要会议论文全文数据库 前10条

1 王翠茹;高丽鲜;;发布订阅系统中匹配算法的研究[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

2 杜云峰;许娜;孙爽;许立永;董彦荣;;一种基于排除的串匹配算法[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年

3 郭莉;刘燕兵;谭建龙;;基于存储压缩的多模式串匹配算法[A];全国第八届计算语言学联合学术会议（JSCL-2005）论文集[C];2005年

4 姚辰松;鲁昌华;;指纹匹配算法的研究[A];全国第19届计算机技术与应用（CACIS）学术会议论文集（上册）[C];2008年

5 宣琦;吴铁军;;复杂网络间节点匹配算法研究[A];2009年第五届全国网络科学论坛论文集[C];2009年

6 龚才春;黄玉兰;许洪波;白硕;;基于多重索引模型的大规模词典近似匹配算法[A];第三届全国信息检索与内容安全学术会议论文集[C];2007年

7 林雪娥;杨鉴;熊艳娇;刘怀憬;李诗心;胡湘兴;;基于拼写规则和最大匹配算法的泰语分词[A];第十二届全国人机语音通讯学术会议（NCMMSC'2013）论文集[C];2013年

8 李晓雷;黄新生;王亦平;徐婉莹;;稳健快速的匹配算法研究[A];'2008系统仿真技术及其应用学术会议论文集[C];2008年

9 姚益平;卢锡城;;基于移动相交信息的动态区域匹配算法[A];仿真计算机与软件、仿真方法与建模学术交流会论文集[C];2004年

10 杨靓;黄巾;卢强;黄士坦;;基于全息相关系数矩阵的匹配算法[A];第十一届全国信号处理学术年会（CCSP-2003）论文集[C];2003年

中国博士学位论文全文数据库 前3条

1 杨容浩;无控制DEM匹配算法性能比较与改进研究[D];西南交通大学;2012年

2 郭克华;基于微分几何的局部相似目标匹配算法研究[D];南京理工大学;2008年

3 汪锦岭;面向Internet的发布/订阅系统的关键技术研究[D];中国科学院研究生院（软件研究所）;2005年

中国硕士学位论文全文数据库 前10条

1 刘芳萍;基于特征匹配的双目立体图像深度提取算法研究[D];上海师范大学;2015年

2 杨腾飞;SIFT匹配算法在遥感影像平面精度评定中的应用[D];昆明理工大学;2015年

3 刘强;多源信息融合框架下辅助导航系统的景象匹配算法研究[D];上海交通大学;2015年

4 钟佩;基于ACS的高阶图匹配算法研究[D];西安电子科技大学;2014年

5 杨扬;面向Web规模图数据的子图匹配算法的研究与实现[D];东北大学;2013年

6 张宏利;云服务中任务分解与匹配算法研究[D];西安工业大学;2013年

7 郜方方;基于内容的发布订阅系统中匹配问题的关键技术研究[D];河南大学;2015年

8 戴昕;高效子图匹配算法研究[D];北京交通大学;2016年

9 来瑾颖;面向发布/订阅的自动化订阅分解模型与匹配算法研究[D];浙江大学;2010年

10 刘香丽;指纹识别中匹配算法的研究[D];湖南大学;2011年

  本文关键词：高效子图匹配算法研究，由笔耕文化传播整理发布。

本文编号：293215