Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks
Proceedings of the ACM on Management of Data · 17.06.2025 · 3 (3) · 1-24
DOI: 10.1145/3725402 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.06.2025. Verfasst von Libin Wang und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 44 Literaturangaben.
Abstract (Originalsprache)
The point-to-point shortest path query is widely used in many spatial applications, e.g., navigation systems. However, the returned shortest path minimizing only one objective fails to satisfy users' various routing requirements in practice. For example, the user may specify the order of using several transportation modes in the planned route. The Label-Constrained Shortest Path (LCSP) query under regular languages is powerful enough to express diversified routing demands in a labeled road network where each edge is associated with a label to denote its road type. The complex routing demand can be formulated by a regular language, and the edge labels along each path should be a word under the given regular language. Previous LCSP solutions were either inefficient in query processing or inflexible in their use of the languages since they made some assumptions about the given language. In this paper, we propose an efficient index-based solution called Border-based State Move (BSM), which can answer LCSP queries quickly with flexible use of the language constraint. Specifically, our BSM builds indexes to skip the exploration between a vertex and its border vertices during query processing. Our experiments conducted on real road networks demonstrated the superiority of our proposed BSM. It can reduce the query time over state-of-the-art solutions by two orders of magnitude.
Zitieren
APA
Wang, L., & Wong, R. C. (2025). Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks. Proceedings of the ACM on Management of Data, 3(3), 1-24. https://doi.org/10.1145/3725402
Vancouver
Wang L, Wong RC. Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks. Proceedings of the ACM on Management of Data. 2025;3(3):1-24. doi:10.1145/3725402
BibTeX
@article{Wang2025,
author = {Wang, Libin and Wong, Raymond Chi-Wing},
title = {Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks},
journal = {Proceedings of the ACM on Management of Data},
year = {2025},
volume = {3},
number = {3},
pages = {1--24},
doi = {10.1145/3725402}
}
EUVIMED