反向时间依赖路网上移动对象的启发式k近邻查询算法

摘要

针对实际应用中用户在真实路网上进行移动服务(如出租车,救护车,外卖等)的查询需求,提出反向时间依赖路网上移动对象的k近邻查询问题.在分析现有查询算法的不足后,建立了反向时间依赖路网和基于标记点的最短路径树.并在此基础上,给出了一种针对反向时间依赖路网上移动对象的k近邻查询算法TDSPT-kNN.通过采用基于最短路径树的启发式函数等剪枝策略,进一步提升查询效率.最后,通过仿真实验对TDSPT-kNN算法和已有算法在多种情况下的对比分析,结果表明相比现有算法,TDSPT-kNN算法查询效率平均提升65.9％,可以高效地处理反向时间依赖路网上移动对象的k近邻查询问题.