动态有向图上面向最短路径查询的新型概要技术研究

摘要

近年来，随着有向图最短路径查询应用在路网、计算机网络和社交网络等数据中的应用不断增加，有向图的最短路径查询技术受到更加广泛的关注。现有技术可以高效的处理无向图环境下的最短路径查询，然而由于有向图上最短路径查询操作的特殊性使得在有向图上的最短路径查询操作遇到了很大的挑战，有向图最短路径查询并无很好的解决方案。本文研究面向有向图准确的和带有精度保证的最短路径查询信息概要技术，并提出动态图环境下相应概要增量维护算法。
　　首先，针对现有有向图最短路径查询技术在计算过程中在精度和速度上的缺陷，本文在代表点策略的基础上提出基于生成树编码概要结构，通过代表点策略降低内存负载极大加快概要构建速度和查询速度;同时针对通过概要结构覆盖全部查询概要结构构建过程中频繁I/O的缺陷，改进其磁盘索引结构提出轻量级的概要结构;在证明准确概要查询结果有效性的前提下，本文提出了相应的I/O高效构建算法和查询算法，并通过实验对准确概要结构性能进行验证。其次，对于用户要求在短时间内获取带有误差保证最短距离的应用请求，本文提出基于拓扑层的离散landmark快速概要结构，通过landmark节点的拓扑层次和相关信息，可以降低搜索数据大小并提前终结不必要的查询，进而加快查询速度;针对查询时在离散landmark节点集合搜索代价较大的缺陷，本文依照二分索引思想组织landmark节点构建近似概要，并针对此概要结构提出近似概要构建算法和有精度保障的查询算法;最终在真实数据集和模拟数据集上进行大量的实验，验证近似概要结构和相应查询算法的有效性。最后，本文对概要结构的高效查询和动态图环境下概要增量维护操作进行研究，为了降低整体查询代价以及动态图环境下概要增量维护代价，本文设计离散磁盘结构存储Triad信息;同时在离散磁盘结构的基础上提出增量维护缓存结构降低平均增量维护代价，并通过摊还分析证明缓存结构的有效性;最后提出基于离散磁盘结构信息获取算法和增量维护算法，并通过实验证明其有效性。
　　本文从实际应用中对有向图最短路径查询的典型特征和调整进行分析，针对有向图最短路径概要相关技术进行研究，提出如代表点策略概要、有精度保障的近似概要以及概要结构增量维护等关键技术处理不同应用场景下的有向图最短路径查询应用。本文的概要结构以更少的内存和更短的预处理时间处理更大规模的图数据，并且以更快的速度返回最短路径查询结果。

目录

声明

摘要

第1章 引言

1．1 图最短路径基本概念及应用

1．2 研究背景

1．2．1 最短路径索引技术

1．2．2 最短路径概要技术

1．3 问题提出

1．4 本文贡献

1．5 本文工作和组织结构

第2章 相关工作概述

2．1 Na?ve最短路径查询策略

2．2 最短路径索引技术

2．2．1 有向图最短路径索引技术

2．2．2 无向图最短路径索引技术

2．3 图概要与图压缩技术

2．3．1 最短路径概要技术

2．3．2 图压缩技术

2．4 结论

第3章 基于代表点策略无损概要

3．1 引言

3．2 C-RTI无损概要模型

3．2．1 基于路径距离主干节点策略概要模型

3．2．2 生成树编码

3．2．3 RTI概要性质

3．3 Q-RTI无损概要

3．3．1 不完备Triad编码

3．3．2 基于覆盖范围均等采样策略

3．4 无损概要构建与查询算法

3．4．1 C-RTI概要构建算法

3．4．2 Q-RTI概要构建策略

3．4．3 Na?ve概要查询算法

3．4．1 概要构建代价分析

3．5 实验

3．5．1 相关技术分析

3．5．2 真实数据集概要性能

3．5．3 模拟数据集概要性能

3．6 结论

第4章 基于拓扑层次近似概要

4．1 引言

4．1．1 传统最短路径快速概要技术

4．1．2 基于无向图近似概要技术缺陷

4．2 Na?ve-TL快速概要模型

4．2．1 离散landmark

4．2．2 Na?ve-TL概要结构

4．3 BTL快速概要

4．3．1 BTL快速概要概述

4．3．2 二分拓扑层次landmark快速概要查询

4．3．3 BTL概要概要构建与查询算法

4．3．4 BTL概要性能

4．4 实验

4．4．1 真实数据集概要性能分析

4．4．2 真实数据集BTL层数对概要性能的影响

4．4．3 模拟数据集BTL概要性能

4．5 结论

第5章 概要高效动态维护与查询

5．1 引言

5．2 离散磁盘概要与查询操作

5．2．1 离散磁盘编码结构

5．2．2 C-RTI／Q-RTI概要查询

5．2．3 BTL概要查询

5．3 动态图概要结构概述

5．3．1 动态图操作分类

5．3．2 概要结构增量维护分析

5．4 基于离散磁盘结构概要维护

5．4．1 C-RTI／Q-RTI概要增量维护

5．4．2 BTL概要更新

5．4．3 增量维护Buffer结构

5．5 实验

5．5．1 真实数据集概要查询与增量计算性能

5．5．2 BTL概要层次数对概要更新代价的影响

5．6 结论

第6章 结论

6．1 本文主要贡献与结论

6．2 进一步的工作

参考文献

致谢

攻读硕士学位期间的项目情况