Trajectory-aware lowest-cost path selection: A summary of results

Yan Li, Pratik Kotwal, Pengyue Wang, Shashi Shekhar, William Northrop

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

Abstract

The trajectory-aware lowest-cost path selection problem aims to find the lowest-cost path using trajectory data. Trajectory data is valuable since it carries information about travel cost along paths, and also reflects travelers' routing preference. Path-centric travel cost estimation models using trajectory data grows popular recently, which considers the auto-correlation of the energy consumption on different segments of a path. However, path-centric models are more computationally expensive than edge-centric models. The main challenge of this problem is that the travel cost of every candidate path explored during the process of searching for the lowest-cost path need to be estimated, resulting in high computational cost. The current path selection algorithms that use path-centric cost estimation models still follow the pattern of “path + edge” when exploring candidate paths, which may result in redundant computation. We introduce a trajectory-aware graph model in which each node is a maximal trajectory-aware path. Two nodes in the trajectory-aware graph are linked by an edge if their union forms a trajectory-union path. We then propose a path selection algorithm to find a path in the proposed trajectory-aware graph which corresponds to the lowest-cost path in the input spatial network. We prove theoretically the proposed algorithm is correct and complete. Moreover, we prove theoretically that the proposed path selection algorithm cost much less computational time than the algorithm used in the related work, and validate it through experiments using real-world trajectory data.

Original languageEnglish (US)
Title of host publicationProceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD 2019
PublisherAssociation for Computing Machinery
Pages61-69
Number of pages9
ISBN (Electronic)9781450362801
DOIs
StatePublished - Aug 19 2019
Event16th International Symposium on Spatial and Temporal Databases, SSTD 2019 - Vienna, Austria
Duration: Aug 19 2019Aug 21 2019

Publication series

NameACM International Conference Proceeding Series

Conference

Conference16th International Symposium on Spatial and Temporal Databases, SSTD 2019
CountryAustria
CityVienna
Period8/19/198/21/19

    Fingerprint

Keywords

  • Path selection
  • Path-centric
  • Routing
  • Shortest path
  • Trajectory

Cite this

Li, Y., Kotwal, P., Wang, P., Shekhar, S., & Northrop, W. (2019). Trajectory-aware lowest-cost path selection: A summary of results. In Proceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD 2019 (pp. 61-69). (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3340964.3340971