Identifying K Primary Corridors from urban bicycle GPS trajectories on a road network

Zhe Jiang, Michael Evans, Dev Oliver, Shashi Shekhar

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


Given a set of GPS tracks on a road network and a number k, the K-Primary-Corridor (KPC) problem aims to identify k tracks as primary corridors such that the overall distance from all tracks to their closest primary corridors is minimized. The KPC problem is important to domains such as transportation services interested in finding primary corridors for public transportation or greener travel (e.g., bicycling) by leveraging emerging GPS trajectory datasets. However, the problem is challenging due to the large amount of shortest path distance computations across tracks. Related trajectory mining approaches, e.g., density or frequency based hot-routes, focus on anomaly detection rather than identifying representative corridors minimizing total distances from other tracks, and thus may not be effective for the KPC problem. Our recent work proposed a k-Primary Corridor algorithm that precomputes a column-wise lookup table of network Hausdorff distances. This paper extends our recent work with a new computational algorithm based on lower bound filtering. We design lower bounds of network Hausdorff distances based on the concept of track envelopes and propose three different track envelope formation strategies based on random selection, overlap, and Jaccard coefficient respectively. Theoretical analysis on proof of correctness as well as computational cost models are provided. Extensive experiments and case studies show that our new algorithm with lower bound filtering significantly reduces the computational time of our previous algorithm, and can help effectively determine primary bicycle corridors.

Original languageEnglish (US)
Pages (from-to)142-159
Number of pages18
JournalInformation Systems
StatePublished - Apr 2016

Bibliographical note

Publisher Copyright:
© 2015 Elsevier Ltd. All rights reserved.


  • Bicycle primary corridors
  • GPS trajectory
  • Lower bound filtering
  • Network Hausdorff distance
  • Road network
  • Spatial data mining
  • Urban data mining


Dive into the research topics of 'Identifying K Primary Corridors from urban bicycle GPS trajectories on a road network'. Together they form a unique fingerprint.

Cite this