Network-Based Trajectory Search over Time Intervals

Abstract In this paper, we study a novel spatio-temporal query over trajectories. The spatial part of the query aims to find the k trajectories closest to the query location, where the closeness is measured by the average shortest-path distance between the trajectory and the query location. The temporal part of the query specifies a time interval. Only those trajectories completely fall into the specified time interval are valid candidates for the query. This novel spatio-temporal query has potential applications in travel planning, POI recommendation, etc. An naive solution to the query is to first find out all the candidate trajectories within the query time interval, and then compute all the exact trajectory-query distances by computing all the shortest-path distances. Such a naive solution is inefficient since it probably searches the entire network for the top-k trajectories. To improve the efficiency, we develop lower and upper bounds for the trajectory-query distance, which can be used to early terminate the search process. Experiments on large, real-life datasets show that our proposed methods outperform the naive search method by a wide margin.