EUVIMEDEUVIMED entdecken
Crossref

EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding

Jinchun Du, Bojie Shen, Muhammad Aamir Cheema

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →