摘要
针对实际应用中用户在真实路网上进行移动服务(如出租车,救护车,外卖等)的查询需求,提出反向时间依赖路网上移动对象的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.
作者
宋力翔
秦小麟
SONG Li-xiang;QIN Xiao-lin
出处
《小型微型计算机系统》
CSCD
北大核心
2021年第7期1532-1538,共7页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61728204)资助。
关键词
K近邻查询
移动对象
时间依赖路网
启发式算法
最短路径树
k nearest neighbor query
mobile object
time-dependent road network
heuristic algorithm
shortest path tree
