基于旅行时间的Top-k轨迹查询

摘要

In order to further improve the existing trajectory query,we propose a top-k trajectory query based on traveling time,which returns k trajectories according to the given query points. The selected k trajectories depend on the user′s interested locations and the traveling time used along the trajectory and k trajectories with shortest traveling time are returned. With grid index,the information of trajectory points is recorded. The Best-First is used to search trajectory points close to query points and the query identifies the effec-tive points to retrieve complete effective trajectories. In order to improve the efficiency of the algorithm,three kinds of termination rules are proposed. Finally,extensive experiments demonstrate the efficiency of our presented algorithms.%为了进一步完善现有的轨迹查询,本文提出一种基于旅行时间的Top-k轨迹查询,给定查询点,可以为用户返回k条轨迹.这k条轨迹的选择依赖于用户感兴趣的位置点和旅行时间,为用户返回k条旅行时间最短的轨迹.针对该查询,提出一种查询算法,利用网格索引来记录轨迹点的信息,算法使用Best-First方法对查询点附近的轨迹点进行检索,并通过判断其是否为有效点来检索完全有效轨迹.为了提高查询效率,提出三种终止规则,其减少了需要访问轨迹点的数量.最后,通过实验验证该算法的有效性.