Path Query Processing Using Typical Snapshots in Dynamic Road Networks

The shortest path query in road network is a fundamental operation in navigation and location-based services. The existing shortest path algorithms aim at improving efficiency in the static/time-dependent environment. However, the real-life road networks are dynamic, so they can hardly meet the requirement in practice. In this paper, we aim to support the path query in dynamic road networks by identifying the typical snapshots from the snapshot sequences, building the path indexes on them, and finally processing the query with the most suitable typical snapshot. Specifically, we first use the typical OD pairs to capture the dynamic information and represent the snapshots. Then the snapshot similarity is measured by considering the shortest path error and the shortest path similarity of these OD pairs. Because the OD pair number is huge and they have different power in capturing the traffic condition, we further propose a hot region-based OD selection method that could select a small but powerful OD set. Lastly, we use the distance-based \(\chi \)-quantile error for the query accuracy evaluation and conduct experiments in a large real-world dynamic road network to verify the effectiveness of our method compared with the state-of-the-art.