Summarizing trajectories into k-primary corridors: A summary of results

Michael R. Evans, Dev Oliver, Shashi Shekhar, Francis Harvey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012
Pages454-457
Number of pages4
DOIs
StatePublished - Dec 1 2012
Event20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012 - Redondo Beach, CA, United States
Duration: Nov 6 2012Nov 9 2012

Other

Other20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012
CountryUnited States
CityRedondo Beach, CA
Period11/6/1211/9/12

Keywords

  • GPS
  • spatial data mining
  • trajectory summarization

Fingerprint Dive into the research topics of 'Summarizing trajectories into k-primary corridors: A summary of results'. Together they form a unique fingerprint.

Cite this