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.
Bibliographical noteFunding Information:
This material is based upon work supported by the National Science Foundation under Grant nos. 1029711 , IIS-1320580 , 0940818 and IIS-1218168 as well as USDOD under Grant no. HM1582-08-1-0017 and HM0210-13-1-0005 . We would like to thank Professor Harvey from the department of Geography, Environment and Social Science of our university for providing datasets and helpful comments in our case studies. We would also like to thank Kim Koffolt for improving the readability of the paper.
© 2015 Elsevier Ltd. All rights reserved.
Copyright 2016 Elsevier B.V., All rights reserved.
- Bicycle primary corridors
- GPS trajectory
- Lower bound filtering
- Network Hausdorff distance
- Road network
- Spatial data mining
- Urban data mining