摘要
随着基于位置服务的广泛应用,时间依赖路网上的对象查询逐渐成为研究热点。以往研究大多只针对时间依赖路网上的静态对象(如加油站、餐厅等),未考虑到移动对象(如出租车)的情况,而移动对象的查询在日常生活中有着非常广泛的应用场景。因此,文中提出了一种针对时间依赖路网上的移动对象K近邻查询算法TD-MOKNN,该算法分为预处理阶段和查询阶段。在预处理阶段,通过建立路网和网格索引,提出了一种新的移动对象到路网的映射方法,解除了以往研究假设移动对象恰好在路网顶点上的限制;在查询阶段,采用启发式搜索,借助倒排网格索引计算了一种新的高效启发值,通过预处理信息和启发值设计了高效K近邻查询算法,并给出了算法的正确性证明和时间复杂度分析。实验验证了所提算法的有效性,相比现有算法,TD-MOKNN算法在遍历顶点数和响应时间上分别减少了55.91%和54.57%,查询效率平均提升了55.2%。
With the wide application of location-based services,object-based query on time-dependent road network has gradually become a research hotspot.In the past,most of the researches only focused on static objects on time-dependent road networks(such as gas stations,restaurants,etc.),and did not take into account the situation of mobile objects(such as taxis).The query of mobile objects has a very wide range of applications in daily life.Therefore,the K nearest neighbor query algorithm TD-MOKNN of moving object is proposed for time-dependent road network.The algorithm is divided into pre-processing stage and query stage.In the pre-processing stage,the road network and grid index are established,and a new mapping method of moving objects to the road network is proposed,which removes the limitation of previous researches that moving objects happen to be on the intersection of the road networks.In the query stage,a new efficient heuristic value is calculated by using inverted grid index,and an efficient k-nearest neighbor query algorithm is designed by using pre-processing information and heuristic value.Experiments verify the effectiveness of the algorithm.Compared with existing algorithm,TD_MOKNN algorithm reduces the number of traversing vertices and response time by 55.91%and 54.57%respectively,and improves the query efficiency by 55.2%on average.
作者
张彤
秦小麟
ZHANG Tong;QIN Xiao-lin(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)
出处
《计算机科学》
CSCD
北大核心
2020年第1期79-86,共8页
Computer Science
基金
国家自然科学基金(61373015,61728204)~~
关键词
K近邻查询
移动对象
时间依赖路网
A^*算法
网格索引
K nearest neighbors query
Moving object
Time-dependent road network
A^*algorithm
Grid index
