历史图数据的存储与计算方法研究
发布时间：2023-04-30 06:25
历史图作为刻画图网络随着时间维度不断的变化的图数据结构,正在越来越多的场景展现其应用和研究价值。本文从历史图数据入手,着手于研究历史图数据的存储和计算方法。基于Rocks DB存储引擎,本文设计并实现了历史图数据库Hist DB对历史图数据进行高效的存储和检索。Hist DB基于K-V存储模式存储历史图的图增量数据,并结合历史图的顶点检索、图增量检索、历史邻居检索和快照检索四类检索设计并实现了高效的数据检索接口。此外,Hist DB基于分块的底层存储,设计了数据索引区块对检索进行优化,实验表明,Hist DB的索引优化机制可以有效地提升一些数据检索接口的性能。本文结合历史图上查询需求,基于Gremlin静态图查询语言并引入时间维度设计了历史图查询语言Hist QL。基于Hist QL语言,本文还设计实现了历史图查询计算框架Hist Query以对查询语句进行计算,Hist Query使用嵌套的计算单元管理方式,可以实现多层次、多粒度的资源管理和计算调度。此外,本文还基于所设计了无锁通信机制,实现了Hist Query的多线程计算框架。本文还基于实验测试,展示了Hist Query的多线...
【文章页数】：75 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第1章 绪论
1.1 课题背景及研究的目的和意义
1.2 历史图数据的相关研究概况
1.2.1 历史图数据存储管理技术的研究概况
1.2.2 历史图数据计算与分析技术的研究概况
1.3 本文的主要研究内容
1.3.1 历史图数据的存储与检索技术
1.3.2 历史图的结构化查询技术
1.3.3 历史图路径分析技术
第2章 历史图数据的存储与检索技术
2.1 引言
2.2 存储原理设计
2.2.1 历史图存储的内在需求和存储引擎选择
2.2.2 底层存储分布与数据写入机制
2.3 数据检索接口设计与检索机制
2.3.1 前缀匹配与迭代器遍历机制
2.3.2 数据检索接口设计
2.3.3 基于索引的检索优化机制
2.4 实验测试与评估
2.4.1 写性能测试
2.4.2 基本迭代器检索性能测试
2.4.3 跳跃迭代器检索性能与索引优化测试
2.5 本章小结
第3章 历史图的结构化查询技术
3.1 引言
3.2 历史图的结构化查询语言设计
3.2.1 结构化查询语言的表示形式
3.2.2 查询算子设计
3.2.3 查询语句示例
3.3 查询计算框架
3.3.1 查询计算框架的内部结构和组织形式
3.3.2 计算数据的信息载体与寻址机制
3.3.3 资源调度与计算流程
3.3.4 查询计算的终止机制
3.4 复杂查询算子实现
3.4.1 条件循环算子
3.4.2 嵌套分支过滤算子
3.5 查询计算的多线程实现
3.5.1 多线程下的计算资源划分
3.5.2 多线程下的查询计算框架结构
3.5.3 多线程无锁通信机制
3.5.4 多线程环境下的计算终止机制
3.6 实验测试与性能评价
3.6.1 数据集
3.6.2 多线程查询性能测试
3.6.3 配置参数的单变量测试
3.6.4 提前终止机制对性能影响的测试
3.6.5 实验总结
3.7 本章小结
第4章 历史图的路径搜索技术
4.1 引言
4.2 历史图的扩展定义
4.3 历史图路径的定义
4.4 历史图路径的效用值定义
4.5 历史图路径搜索问题
4.6 历史图路径搜索基本算法
4.6.1 算法设计与实现
4.6.2 算法复杂性分析
4.7 历史图路径搜索的一趟扫描优化算法
4.7.1 算法设计与实现
4.7.2 算法复杂性分析
4.8 实验测试与评价
4.8.1 实验设置与数据集
4.8.2 算法效率测试
4.8.3 算法的数据敏感性测试
4.9 本章小结
结论
参考文献
攻读硕士学位期间发表的论文及其它成果
致谢
本文编号：3806611
【文章页数】：75 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第1章 绪论
1.1 课题背景及研究的目的和意义
1.2 历史图数据的相关研究概况
1.2.1 历史图数据存储管理技术的研究概况
1.2.2 历史图数据计算与分析技术的研究概况
1.3 本文的主要研究内容
1.3.1 历史图数据的存储与检索技术
1.3.2 历史图的结构化查询技术
1.3.3 历史图路径分析技术
第2章 历史图数据的存储与检索技术
2.1 引言
2.2 存储原理设计
2.2.1 历史图存储的内在需求和存储引擎选择
2.2.2 底层存储分布与数据写入机制
2.3 数据检索接口设计与检索机制
2.3.1 前缀匹配与迭代器遍历机制
2.3.2 数据检索接口设计
2.3.3 基于索引的检索优化机制
2.4 实验测试与评估
2.4.1 写性能测试
2.4.2 基本迭代器检索性能测试
2.4.3 跳跃迭代器检索性能与索引优化测试
2.5 本章小结
第3章 历史图的结构化查询技术
3.1 引言
3.2 历史图的结构化查询语言设计
3.2.1 结构化查询语言的表示形式
3.2.2 查询算子设计
3.2.3 查询语句示例
3.3 查询计算框架
3.3.1 查询计算框架的内部结构和组织形式
3.3.2 计算数据的信息载体与寻址机制
3.3.3 资源调度与计算流程
3.3.4 查询计算的终止机制
3.4 复杂查询算子实现
3.4.1 条件循环算子
3.4.2 嵌套分支过滤算子
3.5 查询计算的多线程实现
3.5.1 多线程下的计算资源划分
3.5.2 多线程下的查询计算框架结构
3.5.3 多线程无锁通信机制
3.5.4 多线程环境下的计算终止机制
3.6 实验测试与性能评价
3.6.1 数据集
3.6.2 多线程查询性能测试
3.6.3 配置参数的单变量测试
3.6.4 提前终止机制对性能影响的测试
3.6.5 实验总结
3.7 本章小结
第4章 历史图的路径搜索技术
4.1 引言
4.2 历史图的扩展定义
4.3 历史图路径的定义
4.4 历史图路径的效用值定义
4.5 历史图路径搜索问题
4.6 历史图路径搜索基本算法
4.6.1 算法设计与实现
4.6.2 算法复杂性分析
4.7 历史图路径搜索的一趟扫描优化算法
4.7.1 算法设计与实现
4.7.2 算法复杂性分析
4.8 实验测试与评价
4.8.1 实验设置与数据集
4.8.2 算法效率测试
4.8.3 算法的数据敏感性测试
4.9 本章小结
结论
参考文献
攻读硕士学位期间发表的论文及其它成果
致谢
本文编号：3806611
本文链接：https://www.wllwen.com/kejilunwen/shengwushengchang/3806611.html
最近更新
教材专著
