A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks

Abstract EN

K nearest neighbor ( k NN) search is an important problem in location-based services (LBS) and has been well studied on static road networks.

However, in real world, road networks are often time-dependent; i.e., the time for traveling through a road always changes over time.

Most existing methods for k NN query build various indexes maintaining the shortest distances for some pairs of vertices on static road networks.

Unfortunately, these methods cannot be used for the time-dependent road networks because the shortest distances always change over time.

To address the problem of k NN query on time-dependent road networks, we propose a novel voronoi-based index in this paper.

Furthermore, we propose a novel balanced tree, named V - t r e e , which is a secondary level index on voronoi-based index to make our querying algorithm more efficient.

Moreover, we propose an algorithm for preprocessing time-dependent road networks such that the waiting time is not necessary to be considered.

We confirm the efficiency of our method through experiments on real-life datasets.