2022/08/18 by Johannes Blum, Blum, Johannes, Sabine Storandt +1
Computer Science · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2208.08709
openalex publication_date 2022/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hub Labeling (HL) is one of the state-of-the-art preprocessing-based techniques for route planning in road networks. It is a special incarnation of distance labeling, and it is well-studied in both theory and practice. The core concept of HL is to associate a label with each vertex, which consists of a subset of all vertices and respective shortest path information, such that the shortest path distance between any two vertices can be derived from considering the intersection of their labels. HL provides excellent query times but requires a time-consuming preprocessing phase. Therefore, in case of edge cost changes, rerunning the whole preprocessing is not viable. Inspired by the concept of Customizable Route Planning, we hence propose in this paper a Customizable Hub Labeling variant for which the edge costs in the network do not need to be known at construction time. These labels can then be used with any edge costs after conducting a so called customization phase. We study the theoretical properties of Customizable Hub Labelings, provide an O(log2 n)-approximation algorithm for the average label size, and propose efficient customization algorithms.