Heuristic-Aided Compressed Distance Databases

Answering point-to-point distance queries is important inmany applications, including games, robotics and vehiclerouting in operations research. Searching in a graph to answer distance queries on demandcan often be too slow.An alternative strategy, taken in methods such asTransit and Hub Labels, is to pre-compute information that can help computedistances much faster.To be practical, such methods need to generate muchless preprocessed data than a naive all-pairs distance table. We present Heuristic-Aid Compressed Distance Databases (HCDs),pre-computed data structures based on the observation thatheuristic 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 ofmaps, reducing the memory usage to a reasonable size. Comparedto compressed path databases, our approachgenerally generates smaller databases, and answers query distances faster.