EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (43) · 36881-36890
DOI: 10.1609/aaai.v40i43.41015 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Jinchun Du und 2 weiteren Autor:innen.
Abstract (Originalsprache)
The Euclidean Shortest Path Problem (ESPP) is a classic problem which requires finding the shortest path in a Euclidean plane with polygonal obstacles. The state-of-the-art solution, Euclidean Hub Labeling (EHL), offers ultra-fast query performance but comes with significant memory overhead, requiring up to tens of gigabytes of storage on large maps, limiting its use in memory-constrained environments like mobile phones. Additionally, EHL's memory usage can only be determined after index construction, and while it provides a memory-runtime tradeoff, it does not fully optimize memory utilization. In this work, we introduce an improved version of EHL, called EHL*, which overcomes these limitations. A key contribution of EHL* is its ability to create an index that adheres to a specified memory budget while optimizing query runtime performance. Moreover, EHL* can leverage pre-known query distributions, a common scenario in many real-world applications, to further enhance runtime efficiency. Our results show that EHL* can reduce memory usage by up to 10-20 times without much impact on query runtime performance compared to EHL, making it a highly effective solution for optimal pathfinding in memory-constrained environments. We also present a theoretical analysis comparing EHL* with EHL, providing insights into their indexing and query processing cost.
Zitieren
APA
Du, J., Shen, B., & Cheema, M. A. (2026). EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 36881-36890. https://doi.org/10.1609/aaai.v40i43.41015
Vancouver
Du J, Shen B, Cheema MA. EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(43):36881-36890. doi:10.1609/aaai.v40i43.41015
BibTeX
@article{Du2026,
author = {Du, Jinchun and Shen, Bojie and Cheema, Muhammad Aamir},
title = {EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {43},
pages = {36881--36890},
doi = {10.1609/aaai.v40i43.41015}
}
EUVIMED