About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
AAAI 2015
Conference paper
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.