### 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 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 |

Pages | 61-69 |

Number of pages | 9 |

ISBN (Electronic) | 9781450362801 |

DOIs | |

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 |

### Publication series

Name | ACM International Conference Proceeding Series |
---|

### Conference

Conference | 16th International Symposium on Spatial and Temporal Databases, SSTD 2019 |
---|---|

Country | Austria |

City | Vienna |

Period | 8/19/19 → 8/21/19 |

### Fingerprint

### Keywords

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

### Cite this

*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