TY - GEN
T1 - Fast and exact network trajectory similarity computation
T2 - 2nd ACM SIGKDD International Workshop on Urban Computing, UrbComp 2013 - Held in Conjunction with the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013
AU - Evans, Michael R.
AU - Oliver, Dev
AU - Shekhar, Shashi
AU - Harvey, Francis
PY - 2013
Y1 - 2013
N2 - Given a set of trajectories on a road network, the goal of the All-Pair Network Trajectory Similarity (APNTS) problem is to calculate the similarity between all trajectories using the Network Hausdorff Distance. This problem is important for a variety of societal applications, such as facilitating greener travel via bicycle corridor identification. The APNTS problem is challenging due to the high cost of computing the exact Network Hausdorff Distance between trajectories in spatial big datasets. Previous work on the APNTS problem takes over 16 hours of computation time on a real-world dataset of bicycle GPS trajectories in Minneapolis, MN. In contrast, this paper focuses on a scalable method for the APNTS problem using the idea of row-wise computation, resulting in a computation time of less than 6 minutes on the same datasets. We provide a case study for transportation services using a data-driven approach to identify primary bicycle corridors for public transportation by leveraging emerging GPS trajectory datasets.
AB - Given a set of trajectories on a road network, the goal of the All-Pair Network Trajectory Similarity (APNTS) problem is to calculate the similarity between all trajectories using the Network Hausdorff Distance. This problem is important for a variety of societal applications, such as facilitating greener travel via bicycle corridor identification. The APNTS problem is challenging due to the high cost of computing the exact Network Hausdorff Distance between trajectories in spatial big datasets. Previous work on the APNTS problem takes over 16 hours of computation time on a real-world dataset of bicycle GPS trajectories in Minneapolis, MN. In contrast, this paper focuses on a scalable method for the APNTS problem using the idea of row-wise computation, resulting in a computation time of less than 6 minutes on the same datasets. We provide a case study for transportation services using a data-driven approach to identify primary bicycle corridors for public transportation by leveraging emerging GPS trajectory datasets.
KW - network hausdorff distance
KW - spatial data mining
KW - trajectory similarity
UR - http://www.scopus.com/inward/record.url?scp=84884160987&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84884160987&partnerID=8YFLogxK
U2 - 10.1145/2505821.2505835
DO - 10.1145/2505821.2505835
M3 - Conference contribution
AN - SCOPUS:84884160987
SN - 9781450323314
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
BT - 2nd International Workshop on Urban Computing, UrbComp 2013 - Held in Conjunction with KDD 2013
Y2 - 11 August 2013 through 11 August 2013
ER -
