Memory-efficient A*-search using sparse embeddings
Franz Graf, Hans‐Peter Kriegel, Matthias Renz, Matthias Schubert · 2010
When searching for optimal paths in a network, algorithms like A*-search need an approximation of the minimal costs between the current node and a target node. A reference node embedding is a universal method for making such an approximation working for any type of positive edge weights. A drawback of the approach is that the memory consumption of the embedding is linearly increasing with the number of attributes and landmarks. In this paper, we propose methods for significantly decreasing the memory consumption of embedded graphs and examine the impact of the landmark selection.