Abstract
Finding the shortest path between two given positions (the origin and the destination) is an essential operation in spatial network databases. Previous studies focus on evaluating the shortest path query, which will find the path with the shortest network distance. However, in the applications on road networks such as the guided driving, the traffic conditions often vary as time goes and the user is actually interested in the path with the minimum travel time (called the fastest path), which may not have the shortest network distance. This motivates us to study the issues of continuously evaluating the fastest path query in order to capture the dynamics of road networks. Repeatedly evaluating the fastest path query at every moment is infeasible due to its computationally expensive cost. The cost is higher if more queries are evaluated at the same time. In this paper, we propose a novel approach that employs the concepts of the affecting area and the tolerance parameter, and a grid-based index structure. With the tolerance parameter, a query is not reevaluated as long as the travel time of the current answer is close enough to that of the fastest path. Furthermore, with the grid-based index, the dynamics of road networks and the queries are fused together to achieve the efficient re-evaluation of multiple queries. Experiments based on real road networks are performed and the results show the great performance of our approach.