论文部分内容阅读
关于路网中近邻查询服务的相关研究,大部分基于欧式距离或路网距离。但在实际应用中,人们对出行的时间成本越来越重视。其中K近邻查询又被广泛应用在路网近邻查询服务中。因此本文针对时间依赖路网中的K近邻查询进行研究,即在边权值随时间不断变化的路网中查询K个兴趣点,使查询点到K个兴趣点的时间最短。根据查询结果的准确度,可将时间依赖路网中的K近邻查询分为K近邻精确查询和K近邻近似查询。首先,针对已有时间依赖路网中K近邻精确查询算法查询效率低的问题。提出PreBF(Precomputation Best-first,PreBF)算法,一种基于预处理和剪枝的K近邻精确查询算法。预处理阶段,通过计算节点最近邻信息表使节点可以快速查询到任意时刻的最近邻。在线计算阶段,利用节点最近邻信息表获得查询点及扩展节点的最近邻,将其作为查询点的K近邻候选集,再根据剪枝技术对候选集进行精确。通过与经典TD-NE算法进行比较,PreBF算法比TD-NE算法响应时间平均减少26.7%,遍历节点个数平均减少约26.84%,实验结果表明,PreBF算法减少了查询扩展的节点个数,降低了查找时间,提高了查询效率。其次,对查询效率较高的时间依赖路网下K近邻近似查询算法TD-FTT(Time Dependent Fast Travel Time,TD-FTT)进行改进。TD-FTT算法查询发起时间与到达K近邻结果的时间必须在同一时段,并且预处理时间代价大。针对以上问题,提出动态选择启发值的改进TD-FTT(ITD-FTT)算法,并利用网络泰森图并行计算节点时段内的最近邻来减少预处理阶段的计算时间。实验结果显示,ITD-FTT算法提高了TD-FTT算法的查询效率,并在预处理阶段计算时间减少了70.12%。最后,应用构建的节点最近邻信息表,提出两种时间依赖路网中K近邻近似查询算法A-PreBF(Approximate Precomputation Best-first,A-PreBF)、PreImd(Precomputation Immediately,PreImd)。并将预计算与启发技术结合,提出Pre-IFTT(Precomputation Fast Travel Time,Pre-IFTT)算法。并保证三种算法的准确率在81.46%到86.42%之间。