-
题名时间依赖路网中限制到达时间的k近邻查询
- 1
-
-
作者
安云哲
倪灿灿
李佳佳
张安珍
夏秀峰
-
机构
沈阳航空航天大学计算机学院
-
出处
《河南科技学院学报（自然科学版）》
2022年第5期58-68,共11页
-
基金
国家自然科学基金青年基金(62102271)。
-
文摘
针对网约车平台中用户希望车辆能够在指定时间内到达的问题,提出了时间依赖路网中限制到达时间的k近邻(Time-dependent k-Nearest Neighbor Query with Limited Arrival Time,TD-Lk NN)查询,目标是返回能够在给定时间段内到达查询点,且车辆的空车时间最少的k个移动对象.首先提出了一种基于网格索引的TIGR(Time-aware Incremental Grid-based restrict)算法,用来获取移动对象的位置,以及限制查询范围.为进一步缩小查询范围以及减小候选集的大小,又提出了三种剪枝策略以及基于剪枝策略的TIGR_P(TIGR with Pruning Strategies)算法.基于对四组纽约真实地图数据进行的实验,验证了所提方法的正确性,以及三种剪枝策略的有效性.结果表明,在六组不同的实验参数下,使用不同的最快路径查询算法来支持TD-Lk NN查询时,TIGR_P算法的查询效率均可以比TIGR算法提升一个数量级左右.
-
关键词
时间依赖路网
限制到达时间
空车时间
K近邻查询
-
Keywords
time-dependent road network
limited arrival time
emptytime
k-nearest neighbor query
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
