论文标题
可自定义的集线器标签：属性和算法
Customizable Hub Labeling: Properties and Algorithms
论文作者
论文摘要
集线器标签（HL）是道路网络中的路线规划的最先进的预处理技术之一。这是距离标签的特殊化身，在理论和实践中都得到了很好的研究。 HL的核心概念是将标签与每个顶点相关联，每个顶点由所有顶点的子集和相应的最短路径信息组成，以便可以从考虑其标签的交汇处得出任何两个顶点之间的最短路径距离。 HL提供了良好的查询时间，但需要耗时的预处理阶段。因此，如果有边缘成本变化，重新阐明整个预处理是不可行的。受到可自定义路线计划的概念的启发，我们在本文中提出了一种可自定义的枢纽标签变体，网络中的优势成本在施工时不需要知道。这些标签可以在执行所谓的自定义阶段后与任何边缘成本一起使用。我们研究了可自定义集线器标签的理论属性，提供了$ \ Mathcal {o}（\ log^2 n）$ - 平均标签大小的近似算法，并提出有效的自定义算法。
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 $\mathcal{O}(\log^2 n)$-approximation algorithm for the average label size, and propose efficient customization algorithms.
