Efficient kNN query for moving objects on time-dependent road networks

Abstract

In this paper, we study the Time-Dependent k Nearest Neighbor (TD-kNN) query on moving objects that aims to return k objects arriving at the query location with the least traveling cost departing at a given time t. Although the kNN query on moving objects has been widely studied in the scenario of the static road network, the TD-kNN query tends to be more complicated and challenging because under the time-dependent road network, the cost of each edge is measured by a cost function rather than a fixed distance value. To tackle such difficulty, we adopt the framework of GLAD and develop an advanced index structure to support efficient fastest travel cost query on time-dependent road network. In particular, we propose the Time-Dependent H2H (TD-H2H) index, which pre-computes the aggregated weight functions between each node to some specific nodes in the decomposition tree derived from the road network.