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