Discovering pattern-aware routes from trajectories

Abstract

With the prevalence of GPS-equipped devices and navigation services, users can record and share their driving movements via trajectories. These trajectories reveal users\' driving behaviors for planning routes. In this paper, we propose a novel pattern-aware route discovery framework that considers users\' preferred routes. The proposed framework is comprised of two components: pattern-aware road map generation and route planning. In the first component, we mine significant road segments from historical trajectories, and generate a pattern-aware road map. We design a route score function that strikes a balance between user preference degrees and the length of the route. For the second component, given a source, a destination, and a user pre-defined value k, we intend to derive the top-k routes that consist of road segments from the source to the destination in the pattern-aware road map. To support on-line route planning in most navigation services, we propose a constrained breadth-first-search (CBFS) algorithm. We evaluate the performance of our framework using real trajectory data, and compare our framework with an existing approach in terms of effectiveness and efficiency. The experimental results demonstrate the effectiveness and efficiency of our proposed framework.