Heuristic-aided compressed distance databases

Abstract

Answering point-to-point distance queries is important in many applications, including games, robotics and vehicle routing in operations research. Searching in a graph to answer distance queries on demand can often be too slow. An alternative strategy, taken in methods such as Transit and Hub Labels, is to pre-compute information that can help compute distances much faster. To be practical, such methods need to generate much less preprocessed data than a naive all-pairs distance table. We present Heuristic-A id Compressed Distance Databases (HCDs), pre-computed data structures based on the observation that heuristic distance estimations can sometimes coincide with true distances. Compared to a naive all-pairs distance table, we report compression factors of two to three orders of magnitude in a wide range of maps, reducing the memory usage to a reasonable size. Compared to compressed path databases, our approach generally generates smaller databases, and answers query distances faster.