大规模DAG图可达查询与优化方法研究

发布时间：2017-05-13 13:10

  本文关键词：大规模DAG图可达查询与优化方法研究，由笔耕文化传播整理发布。

【摘要】：图作为一种能描述复杂结构化的通用数据结构,被广泛应用于XML数据库、社会关系网络、地理导航和本体查询等新兴领域。随着信息技术中图数据的极速增长,图数据结构变得日益复杂,图数据的分析、存储和管理均面临前所未有的挑战。作为大规模DAG图数据分析中最常见的技术,可达查询扮演着一个最基础的角色。然而大部分现有的可达查询机制在面对大规模图时呈现查询效率低的问题。因此,针对大规模DAG图能否高效地进行可达查询和优化对管理图数据库是至关重要的。针对上述问题,本文对大规模DAG图的可达查询和优化方法进行了深入研究。首先提出了一种基于图分层的标签索引方法(GSL,Graph Stratification Labeling),该方法将图分层技术应用到预处理过程中,利用二分图的最大匹配图性质将分层后各节点集链接成一条条不相交的链式结构,进而将大规模图压缩至最小化,最后根据各节点的性质和节点间的可达关系,为图中节点分别创建其独有的链内标签和链间标签。其次,基于GSL索引方法提出了两种新的可达查询方法:链内可达查询方法和链间可达查询方法。同时基于图分层和最大匹配图算法的性质,提出了两种可达查询优化方法:基于图分层性质的优化方法和基于传递性的优化方法。最后,通过在模拟数据集和真实数据集上将本文的可达查询算法,及其索引算法和现有的算法进行实验比较和分析,验证了本文提出的可达查询方法在现实图网络、大规模稀疏图和稠密图上都具有很好的查询性能,大大的提高可达查询的效率。
【关键词】：大规模DAG图 可达性查询 图分层 最大匹配图 标签索引方法
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP311.13
【目录】：

• 摘要4-5
• ABSTRACT5-10
• 第1章 引言10-16
• 1.1 研究背景10-12
• 1.2 国内外研究现状12-13
• 1.3 研究内容13-14
• 1.4 本文组织结构14-16
• 第2章 可达查询相关方法16-24
• 2.1 传统方法16
• 2.2 中小规模图的可达查询16-21
• 2.2.1 链分解方法16-18
• 2.2.2 树覆盖方法18-19
• 2.2.3 路径树方法19-20
• 2.2.4 Hop编码方法20-21
• 2.3 大规模图的可达查询21-23
• 2.4 本章小结23-24
• 第3章 基于图分层的标签索引方法24-36
• 3.1 索引方法概述24-25
• 3.2 图分层25-28
• 3.2.1 基本符号定义25-26
• 3.2.2 图分层算法26-28
• 3.3 创建最大匹配图28-33
• 3.3.1 相关概念28-30
• 3.3.2 创建最大匹配图算法30-33
• 3.4 生成可达标签33-35
• 3.5 本章小结35-36
• 第4章 基于GSL的可达查询方法36-46
• 4.1 问题定义36
• 4.2 链内可达查询36-39
• 4.3 链间可达查询39-41
• 4.4 可达查询优化41-45
• 4.4.1 基于图分层性质的优化41-43
• 4.4.2 基于传递性的优化43-45
• 4.5 本章小结45-46
• 第5章 实验及分析46-54
• 5.1 实验环境介绍46
• 5.2 实验数据集46-47
• 5.2.1 模拟数据集47
• 5.2.2 真实数据集47
• 5.3 性能评估指标47-48
• 5.4 实验结果分析48-53
• 5.4.1 模拟数据集实验48-51
• 5.4.2 真实数据集实验51-53
• 5.5 本章小结53-54
• 第6章 总结与展望54-56
• 6.1 总结54-55
• 6.2 展望55-56
• 致谢56-57
• 参考文献57-60
• 攻读学位期间发表的学术论文及参加科研情况60-61

【参考文献】

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

1 舒虎;崇志宏;倪巍伟;卢山;徐立臻;;X-Hop:传递闭包的多跳数压缩存储和快速可达性查询[J];计算机科学;2012年03期

2 袁野;王国仁;;基于阈值的概率图可达查询[J];计算机学报;2010年12期

3 范时平;潘淑琴;罗启涵;;一种新的基于递归分解的图可达性查询算法[J];计算机应用研究;2014年12期

4 富丽贞;孟小峰;;大规模图数据可达性索引技术:现状与展望[J];计算机研究与发展;2015年01期

5 李鸣鹏;高宏;邹兆年;;基于图压缩的k可达查询处理[J];软件学报;2014年04期

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

1 史岭峰;基于社交网络好友关系的图查询算法研究与应用[D];南京理工大学;2012年

  本文关键词：大规模DAG图可达查询与优化方法研究，，由笔耕文化传播整理发布。

本文编号：362628