TY - GEN

T1 - Summarizing trajectories into k-primary corridors

T2 - 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012

AU - Evans, Michael R.

AU - Oliver, Dev

AU - Shekhar, Shashi

AU - Harvey, Francis

PY - 2012

Y1 - 2012

N2 - Given a set of GPS trajectories on a road network, the goal of the k-Primary Corridors (k-PC) problem is to summarize trajectories into k groups, each represented by its most central trajectory. This problem is important to a variety of 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. Related trajectory mining approaches, e.g., density or frequency based hot-routes, focus on anomaly detection rather than summarization and may not be effective for the k-PC problem. The k-PC problem is challenging due to the computational cost of creating the track similarity matrix. A naïve graph-based approach to compute a single element of this track similarity matrix requires multiple invocations of common shortest-path algorithms (e.g., Dijkstra). To reduce the computational cost of creating this track similarity matrix, we propose a novel algorithm that switches from a graph-based view to a matrix-based view, computing each element in the matrix with a single invocation of a shortest-path algorithm. Experimental results show that these ideas substantially reduce computational cost without altering the results.

AB - Given a set of GPS trajectories on a road network, the goal of the k-Primary Corridors (k-PC) problem is to summarize trajectories into k groups, each represented by its most central trajectory. This problem is important to a variety of 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. Related trajectory mining approaches, e.g., density or frequency based hot-routes, focus on anomaly detection rather than summarization and may not be effective for the k-PC problem. The k-PC problem is challenging due to the computational cost of creating the track similarity matrix. A naïve graph-based approach to compute a single element of this track similarity matrix requires multiple invocations of common shortest-path algorithms (e.g., Dijkstra). To reduce the computational cost of creating this track similarity matrix, we propose a novel algorithm that switches from a graph-based view to a matrix-based view, computing each element in the matrix with a single invocation of a shortest-path algorithm. Experimental results show that these ideas substantially reduce computational cost without altering the results.

KW - GPS

KW - spatial data mining

KW - trajectory summarization

UR - http://www.scopus.com/inward/record.url?scp=84872768020&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84872768020&partnerID=8YFLogxK

U2 - 10.1145/2424321.2424388

DO - 10.1145/2424321.2424388

M3 - Conference contribution

AN - SCOPUS:84872768020

SN - 9781450316910

T3 - GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems

SP - 454

EP - 457

BT - 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012

Y2 - 6 November 2012 through 9 November 2012

ER -