Discovering pattern-aware routes from trajectories

Ling Yin Wei*, Kai Ping Chang, Wen-Chih Peng

*Corresponding author for this work

Research output: Contribution to journalArticle

5 Scopus citations

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.

Original languageEnglish
Pages (from-to)201-226
Number of pages26
JournalDistributed and Parallel Databases
Volume33
Issue number2
DOIs
StatePublished - 1 Jun 2015

Keywords

  • Data mining
  • Geographic information system
  • Location-based services
  • Trajectory database
  • Trip planning

Fingerprint Dive into the research topics of 'Discovering pattern-aware routes from trajectories'. Together they form a unique fingerprint.

  • Cite this