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

详细信息    查看全文

• 作者：Zhe Jiang ; ^{zhe@cs.umn.edu" class="auth_mail" title="E-mail the corresponding author} ; Michael Evans ^{mevans@cs.umn.edu" class="auth_mail" title="E-mail the corresponding author} ; Dev Oliver ^{dev@cs.umn.edu" class="auth_mail" title="E-mail the corresponding author} ; Shashi Shekhar ^{shekhar@cs.umn.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Spatial data mining ; Urban data mining ; GPS trajectory ; Road network ; Network Hausdorff distance ; Lower bound filtering ; Bicycle primary corridors
• 刊名：Information Systems
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：57
• 期：Complete
• 页码：142-159
• 全文大小：8935 K

文摘

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.