时间序列图中最优路径查询方法研究

发布时间：2019-09-18 04:16

【摘要】：最短路径查询是图领域中研究的一个重要课题,用于计算一个顶点到其他顶点的最短路径,应用非常的广泛。主要特点是由起始顶点出发,向外逐层遍历,扩展到目标终点结束。经典最短路径查询通常是定义在静态图中,发展至今已有很多成熟高效的求解算法。然而在当今许多现实应用中,图模型往往具有时间特性,例如时间序列图。经典最短路径查询算法在面对此类图模型时遇到了很大的挑战,往往不能给出满足查询条件的最优解决方案。本文研究分析时间序列图中的路径查询问题,针对其时间特性,提出了最优路径查询算法。同时考虑到大数据环境下图的规模将日益扩大,因此对算法进行了扩展,提出了一种基于Hadoop的分布式查询算法。首先,本文对时间序列图的概念及特性进行了描述,同时基于时间代价和费用代价的考虑,定义了五种“最优”路径:最早到达路径、最晚出发路径、最少用时路径、最少中转路径、最小费用路径,并且提出了时间序列图的入边表示法。其次,针对经典最短路径查询算法的不足,本文提出了一种基于时间序列图的最优路径查询算法。算法采用基于条件约束的中途顶点尽早淘汰策略,使用反向搜索的方式,由目标顶点向出发顶点反向逐级推进,有效的提高了查询效率。同时,考虑到随着信息技术的发展,图的规模将日益扩大,集中式的解决方案不能满足大规模时间序列图的查询需求。因此,本文针对大数据环境下大规模时间序列图的查询,对最优路径查询算法进行了扩展,采用MapReduce编程模型,提出了一种基于Hadoop的分布式计算方法。最后分别在集中式和分布式环境中进行了实验。实验结果表明,本文提出的两种最优路径查询方法均具有较高的执行效率和准确性。
【图文】：

时间序列,时间序列,出发时间,路径

12图 3-1 时间序列图示，对于任意的 i（1 < i ≤ k），将边i e =的元素组合连接成五元组( i i i+v ,d ,v 0iw ，iw 为第 i 个顶点iv 的等待时要等待iw 时间，才能于时间id 出发。定义：对于任意的 i（1 < i ≤ k），路径 P。同时定义： ( ) ( )k karrive P = d t，即路径 P 的出发时间；d ura (P ) = arr

示意图,索引,时间序列,查询算法

14图 3-2 时间序列图的入边索引示意图3.2 基于时间序列图的最优路径查询算法3.2.1 最优路径查询算法时间序列图的时间特性和费用特性决定了计算得到的路径如果没有满足最优路径查询的时间条件和费用条件，则选取的路径是完全没有意义的。因此，本节基于时间序列图的相关概念，结合基于条件约束的中途顶点尽早淘汰策略，提出最优路径查询算法 OPQA（Optimal Path Query Algorithm）。最优路径查询算法包含两个阶段。第一个阶段为反向搜索阶段，，即执行基于代价限制的反向
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】