King's College London

Research portal

Improving the Cache-Efficiency of Shortest Path Search

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Original languageEnglish
Title of host publicationKI 2017: Advances in Artificial Intelligence - 40th Annual German Conference on AI, Proceedings
PublisherSpringer Verlag
Pages99-113
Number of pages15
Volume10505 LNAI
ISBN (Electronic)978-3-319-67190-1
ISBN (Print)9783319671895
DOIs
Publication statusE-pub ahead of print - 19 Sep 2017
Event40th Annual German Conference on Artificial Intelligence, KI 2017 - Dortmund, Germany
Duration: 25 Sep 201729 Sep 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10505 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference40th Annual German Conference on Artificial Intelligence, KI 2017
CountryGermany
CityDortmund
Period25/09/201729/09/2017

King's Authors

Abstract

Flood-filling algorithms as used for coloring images and shadow casting show that improved locality greatly increases the cache performance and, in turn, reduces the running time of an algorithm. In this paper we look at Dijkstra’s method to compute the shortest paths for example to generate pattern databases. As cache-improving contributions, we propose edge-cost factorization and flood-filling the memory layout of the graph. We conduct experiments in commercial game maps and compare the new priority queues with advanced heap implementations as well as and with alternative bucket implementations.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454