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 language||English (US)|
|Title of host publication||Proceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD 2019|
|Publisher||Association for Computing Machinery|
|Number of pages||9|
|State||Published - Aug 19 2019|
|Event||16th International Symposium on Spatial and Temporal Databases, SSTD 2019 - Vienna, Austria|
Duration: Aug 19 2019 → Aug 21 2019
|Name||ACM International Conference Proceeding Series|
|Conference||16th International Symposium on Spatial and Temporal Databases, SSTD 2019|
|Period||8/19/19 → 8/21/19|
Bibliographical noteFunding Information:
This material is based upon work supported by the National Science Foundation under Grants No. 1541876, 1029711, IIS-1320580, IIS-0940818, and IIS-1218168, the USDOD under Grants No. HM1582-08-1-0017 and HM0210-13-1-0005, the Advanced Research Projects Agency-Energy (ARPA-E), U.S. Department of Energy under Award No. DE-AR0000795, the NIH under Grant No. UL1 TR002494, KL2 TR002492, and TL1 TR002493, the USDA under Grant No. 2017-51181-27222, and the OVPR Infrastructure Investment Initiative and Minnesota Supercomputing Institute (MSI) at the University of Minnesota. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or any agency thereof. The authors would like to thank Kim Koffolt and the University of Minnesota Spatial Computing Research Group for their comments.
© 2019 Association for Computing Machinery.
- Path selection
- Shortest path