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

Heuristic k Nearest Neighbor Queries of Moving Objects in Reverse Time-dependent Road Networks

作　　者：宋力翔 秦小麟[1] SONG Li-xiang;QIN Xiao-lin

机构地区：[1]南京航空航天大学计算机技术与科学学院,南京210016

出　　处：《小型微型计算机系统》2021年第7期1532-1538,共7页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61728204)资助。

摘　　要：针对实际应用中用户在真实路网上进行移动服务(如出租车,救护车,外卖等)的查询需求,提出反向时间依赖路网上移动对象的k近邻查询问题.在分析现有查询算法的不足后,建立了反向时间依赖路网和基于标记点的最短路径树.并在此基础上,给出了一种针对反向时间依赖路网上移动对象的k近邻查询算法TDSPT-k NN.通过采用基于最短路径树的启发式函数等剪枝策略,进一步提升查询效率.最后,通过仿真实验对TDSPT-k NN算法和已有算法在多种情况下的对比分析,结果表明相比现有算法,TDSPT-k NN算法查询效率平均提升65.9%,可以高效地处理反向时间依赖路网上移动对象的k近邻查询问题.In view of the actual application needs of users to query mobile services(such as taxi,ambulance takeaway,etc.)on the real road network,the k nearest neighbor query problem of reverse time-dependent mobile objects on the road network is proposed.After analyzing the deficiencies of existing query algorithms,the reverse time-dependent road network and the shortest path tree based on marked points are established.Based on this,a K-nearest neighbor query algorithm TDSPT-kNN for moving objects on the reverse time-dependent road network is given.By using pruning strategies such as heuristic functions based on the shortest path tree,query efficiency is further improved.Finally,through a simulation experiment,the TDSPT-kNN algorithm and the existing algorithm are compared and analyzed in various situations.The results show that the query efficiency of the TDSPT-kNN algorithm is improved by 65.9%on average compared with the existing algorithm,which can be efficiently processed Reverse time depends on the k nearest neighbor query problem of moving objects on the road.

关 键 词：K近邻查询 移动对象 时间依赖路网 启发式算法 最短路径树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]