大规模图上扩展的个性化子图搜索问题研究
发布时间：2021-02-21 09:21
图模型以点和边描述实体和关系,相较于其他数据结构,更能简洁有力的刻画事务之间的复杂关系,因此被广泛应用于众多领域求解实际问题。随着当今时代数据量的大规模增长,以大规模图为模型的问题求解受到越来越多的关注,而子图搜索问题作为图论的重要子问题之一,具有深远的研究意义和价值。目前的子图搜索问题求解算法,大多仅适用于无权图,且在大规模数据图上的执行效果并不十分理想。尽管近年来,部分研究提出并行求解大规模图上的子图搜索,但已有的算法对于一些常见限定性查询执行效率极低,甚至无法满足查询需求。本文针对子图搜索问题中的一类限定性查询进行创新和改进,主要研究内容如下:在已有的个性化子图搜索问题上做扩展并进行形式化定义。现有的子图搜索问题中查询图节点均具有唯一属性值,个性化子图搜索问题同时要求部分区域的权值大于用户设定的阈值。而在扩展的个性化子图搜索问题中,查询图的节点分为两类:一类节点的属性值唯一;另一类节点的属性值具有可选择性。数据图的节点属性值均唯一。扩展的个性化子图搜索即在数据图中寻找子图满足:1)查询图中第一类节点的属性值与子图相应节点的属性值相同;2)查询图中第二类节点的属性值之一与子图相应节...
【文章来源】：中南民族大学湖北省
【文章页数】：53 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第1章 绪论
1.1 研究背景及意义
1.2 国内外研究现状
1.3 本文主要工作
1.4 本文组织结构
第2章 子图搜索相关理论及技术
2.1 图相关定义
2.1.1 图模型
2.1.2 子图搜索
2.1.3 个性化子图搜索问题
2.2 图索引技术
2.3 分布式技术
2.3.1 MapReduce计算模型
2.3.2 Hadoop框架
2.4 本章小结
第3章 基于双索引的多样性子图搜索算法
3.1 多样性子图搜索问题
3.2 索引的构建
3.2.1 CP索引
3.2.2 Vin索引
3.3 多样性子图搜索算法
3.3.1 DSSA算法
3.3.2 优化策略
3.3.3 算法分析
3.4 实验
3.4.1 实验环境和数据集
3.4.2 节点规模对效率的影响
3.4.3 多值节点的节点值规模对效率的影响
3.5 本章小结
第4章 多样性子图搜索算法的并行化实现
4.1 问题分析
4.1.1 数据图划分问题
4.1.2 边界子图匹配问题
4.2 数据图处理
4.2.1 基于定值域的数据图划分
4.2.2 基于边界边的索引构建
4.2.3 DLP算法
4.3 PDSSA算法
4.3.1 PDSSA描述
4.3.2 PDSSA map阶段
4.3.3 PDSSA reduce阶段
4.4 实验
4.4.1 实验环境和数据集
4.4.2 DLP实验结果及分析
4.4.3 PDSSA实验结果及分析
4.5 本章小结
第5章 总结与展望
5.1 本文总结
5.2 未来工作展望
参考文献
附录A 攻读学位期间获得的成果及参加的项目
致谢
【参考文献】：
期刊论文
[1]图数据分析系统计算模型综述[J]. 刘梦雅,刘燕兵,于静,郭莉,孙志刚. 计算机应用研究. 2017(11)
[2]云计算中Hadoop技术研究与应用综述[J]. 夏靖波,韦泽鲲,付凯,陈珍. 计算机科学. 2016(11)
[3]大规模数据图上的个性化子图匹配算法[J]. 杨艳,纪安娜,金虎. 计算机研究与发展. 2015(S1)
[4]大规模图数据匹配技术综述[J]. 于静,刘燕兵,张宇,刘梦雅,谭建龙,郭莉. 计算机研究与发展. 2015(02)
[5]图数据表示与压缩技术综述[J]. 张宇,刘燕兵,熊刚,贾焰,刘萍,郭莉. 软件学报. 2014(09)
[6]图索引技术研究综述[J]. 刘雅辉,刘春阳,张铁赢,程学旗. 山东大学学报(理学版). 2013(11)
[7]MapReduce并行编程模型研究综述[J]. 李建江,崔健,王聃,严林,黄义双. 电子学报. 2011(11)
[8]云计算环境下的大规模图数据处理技术[J]. 于戈,谷峪,鲍玉斌,王志刚. 计算机学报. 2011(10)
[9]基于消息传递机制的MapReduce图算法研究[J]. 潘巍,李战怀,伍赛,陈群. 计算机学报. 2011(10)
博士论文
[1]图数据查询技术的研究[D]. 李先通.哈尔滨工业大学 2009
硕士论文
[1]基于Spark的子图匹配算法研究与实现[D]. 郭腾.北京交通大学 2017
[2]高效子图匹配算法研究[D]. 戴昕.北京交通大学 2016
本文编号：3044151
【文章来源】：中南民族大学湖北省
【文章页数】：53 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第1章 绪论
1.1 研究背景及意义
1.2 国内外研究现状
1.3 本文主要工作
1.4 本文组织结构
第2章 子图搜索相关理论及技术
2.1 图相关定义
2.1.1 图模型
2.1.2 子图搜索
2.1.3 个性化子图搜索问题
2.2 图索引技术
2.3 分布式技术
2.3.1 MapReduce计算模型
2.3.2 Hadoop框架
2.4 本章小结
第3章 基于双索引的多样性子图搜索算法
3.1 多样性子图搜索问题
3.2 索引的构建
3.2.1 CP索引
3.2.2 Vin索引
3.3 多样性子图搜索算法
3.3.1 DSSA算法
3.3.2 优化策略
3.3.3 算法分析
3.4 实验
3.4.1 实验环境和数据集
3.4.2 节点规模对效率的影响
3.4.3 多值节点的节点值规模对效率的影响
3.5 本章小结
第4章 多样性子图搜索算法的并行化实现
4.1 问题分析
4.1.1 数据图划分问题
4.1.2 边界子图匹配问题
4.2 数据图处理
4.2.1 基于定值域的数据图划分
4.2.2 基于边界边的索引构建
4.2.3 DLP算法
4.3 PDSSA算法
4.3.1 PDSSA描述
4.3.2 PDSSA map阶段
4.3.3 PDSSA reduce阶段
4.4 实验
4.4.1 实验环境和数据集
4.4.2 DLP实验结果及分析
4.4.3 PDSSA实验结果及分析
4.5 本章小结
第5章 总结与展望
5.1 本文总结
5.2 未来工作展望
参考文献
附录A 攻读学位期间获得的成果及参加的项目
致谢
【参考文献】：
期刊论文
[1]图数据分析系统计算模型综述[J]. 刘梦雅,刘燕兵,于静,郭莉,孙志刚. 计算机应用研究. 2017(11)
[2]云计算中Hadoop技术研究与应用综述[J]. 夏靖波,韦泽鲲,付凯,陈珍. 计算机科学. 2016(11)
[3]大规模数据图上的个性化子图匹配算法[J]. 杨艳,纪安娜,金虎. 计算机研究与发展. 2015(S1)
[4]大规模图数据匹配技术综述[J]. 于静,刘燕兵,张宇,刘梦雅,谭建龙,郭莉. 计算机研究与发展. 2015(02)
[5]图数据表示与压缩技术综述[J]. 张宇,刘燕兵,熊刚,贾焰,刘萍,郭莉. 软件学报. 2014(09)
[6]图索引技术研究综述[J]. 刘雅辉,刘春阳,张铁赢,程学旗. 山东大学学报(理学版). 2013(11)
[7]MapReduce并行编程模型研究综述[J]. 李建江,崔健,王聃,严林,黄义双. 电子学报. 2011(11)
[8]云计算环境下的大规模图数据处理技术[J]. 于戈,谷峪,鲍玉斌,王志刚. 计算机学报. 2011(10)
[9]基于消息传递机制的MapReduce图算法研究[J]. 潘巍,李战怀,伍赛,陈群. 计算机学报. 2011(10)
博士论文
[1]图数据查询技术的研究[D]. 李先通.哈尔滨工业大学 2009
硕士论文
[1]基于Spark的子图匹配算法研究与实现[D]. 郭腾.北京交通大学 2017
[2]高效子图匹配算法研究[D]. 戴昕.北京交通大学 2016
本文编号：3044151
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3044151.html
