大图上的k步可达查询研究

目录

第1章 绪论

1.1 研究背景

1.2 研究现状

1.2.1 可达性查询的研究

1.2.2 k步可达查询的研究

1.3 本文主要研究内容

1.4 文章结构

第2章 基础知识概述

2.1 k步可达性的相关概念

2.1.1 图的基本概念

2.1.2 可达性的基本概念

2.2 k步可达性的相关算法

2.2.1 基于图遍历求解算法

2.2.2 基于区间标签求解方法

2.2.3 基于最短路径求解方法

2.2.4 基于k步索引求解方法

2.2.5 基于复合索引的求解方法

2.3 本章小结

第3章 k步可达索引及其构建

3.1 问题分析

3.2 基于hop点的可达索引

3.2.1 索引结构

3.2.2 索引优化

3.2.3 索引构建

3.2.4 算法描述

3.2.5 复杂度分析

3.3 基于覆盖率的可达索引

3.3.1 问题分析

3.3.2 索引结构

3.3.3 索引构建

3.3.4 优化方案

3.3.5 算法描述

3.3.6 复杂度分析

3.4 基于拓扑层的不可达索引

3.4.1 问题分析

3.4.2 索引结构

3.4.3 索引构建

3.4.4 算法描述

3.4.5 优化方案

3.4.6 复杂度分析

3.5 本章小结

第4章 查询算法

4.1 问题分析

4.2 高效的剪枝策略

4.2.1 不可达查询的优化

4.2.2 提前终止策略

4.3 查询优化策略

4.3.1 双向搜索策略

4.3.2 远距离优先策略

4.4 查询算法设计

4.5 本章小结

第5章 实验

5.1 实验配置

5.2 数据集及评价标准

5.3 优化策略实验

5.3.1 可达覆盖率对算法的影响实验

5.3.2 拓扑号和查询策略的优化

5.3.3 查询时间比较

5.3.4 索引构建时间和索引大小

5.4 本章小结

第6章 总结与展望

6.1 总结

6.2 展望

攻读学位期间的研究成果目录

参考文献