Memory-restricted Routing With Tiled Map Data
- Modern routing algorithms reduce query time by depending heavily on preprocessed data. The recently developed Navigation Data Standard (NDS) enforces a separation between algorithms and map data, rendering preprocessing inapplicable. Furthermore, map data is partitioned into tiles with respect to their geographic coordinates. With the limited memory found in portable devices, the number of tiles loaded becomes the major factor for run time. We study routing under these restrictions and present new algorithms as well as empirical evaluations. Our results show that, on average, the most efficient algorithm presented uses more than 20 times fewer tile loads than a normal A*.
| Author details: | Thomas BlaesiusGND, Jan Eube, Thomas Feldtkeller, Tobias FriedrichORCiDGND, Martin Stefan KrejcaORCiDGND, Gregor J. A. LagodzinskiORCiD, Ralf RothenbergerORCiDGND, Julius Severin, Fabian Sommer, Justin TrautmannORCiD |
|---|---|
| DOI: | https://doi.org/10.1109/SMC.2018.00567 |
| ISBN: | 978-1-5386-6650-0 |
| ISSN: | 1062-922X |
| Title of parent work (English): | 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC) |
| Publisher: | IEEE |
| Place of publishing: | New York |
| Publication type: | Other |
| Language: | English |
| Year of first publication: | 2018 |
| Publication year: | 2018 |
| Release date: | 2022/02/24 |
| Number of pages: | 8 |
| First page: | 3347 |
| Last Page: | 3354 |
| Organizational units: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
| Peer review: | Referiert |
