大图上高效的子图匹配算法设计与实现

摘要

在大数据时代，海量多源异构数据之间存在着复杂、紧密的关系，用图结构作为描述数据间复杂的关系被广泛应用于各个领域。但是，随着这些领域的蓬勃发展，以图为结构的数据量也呈指数型爆炸式增长。而子图匹配作为图数据处理中的一项基本操作，备受学术界和工业界所关注。如何根据用户自定义的查询结构，在大规模数据图上高效地返回满足用户要求的匹配成为目前首要研究问题。然而，之前的工作，多数都是在无权图上的查询，并没有考虑用户的个性化需求，并且目前算法在大规模数据图上的执行时间和效果并不是很理想。本文对目前子图匹配问题中的存在的不足进行了改进和创新，主要研究成果及贡献如下:
　　对于大规模数据图上的个性化子图匹配算法进行研究，首先通过已有的社团检测GN算法将数据图划分成若干个子区域，2个线下索引结构:GP-Tree索引和排序边集索引;然后基于索引结构，通过增加优化策略来加速子图匹配;最后，通过实验证明了该算法的有效性和扩展性。
　　对于大规模数据图上的并行子图匹配算法进行研究，利用SparkGraphX中的顶点划分算法将数据图进行划分，保证每台计算机上数据的负载均衡;并通过建立GP邻接索引和排序边集索引，在Spark集群上来实现并行子图匹配算法;最后，通过大量实验验证该算法在大规模数据图上的高效性和扩展性。

目录

摘要

第1章 绪论

1．1 子图匹配问题概述

1．1．1 子图匹配的研究背景

1．1．2 子图匹配的研究目的与意义

1．2 子图匹配问题的研究现状

1．3 本文主要研究内容及章节安排

1．3．1 本文主要研究内容

1．3．2 本文章节安排

第2章 相关基础知识

2．1 子图匹配的相关问题定义

2．1．1 数据图和查询图

2．1．2 子图匹配问题定义

2．2 经典子图匹配算法

2．2．1 SPath算法

2．2．2 RWM算法

2．3 本章小结

第3章 大图上的个性化子图匹配算法的设计与实现

3．1 线下索引的构建

3．1．1 GP-Tree索引

3．1．2 SL索引

3．2 个性化子图匹配算法

3．2．1 PSM算法概述

3．2．2 GPSearch搜索算法

3．2．3 PerSubMatch匹配算法

3．3 实验

3．3．1 实验设置

3．3．2 实验结果及分析

3．4 本章小结

第4章 大图上的并行子图匹配算法的设计与实现

4．1 线下索引的构建

4．1．1 GP邻接索引

4．1．2 PSL索引

4．2 并行子图匹配算法

4．2．1 Par_PSM算法概述

4．2．2 PartitionQuery算法

4．2．3 IsCandiate算法

4．3 实验

4．3．1 实验设置

4．3．2 实验结果及分析

4．4 本章小结

结论

参考文献

致谢

攻读硕士学位期间发表的学术论文

声明