Recent Results on Hub Labeling
Andrew V. Goldberg · 2014
.Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle design is to precompute a label for every vertex so that the distances can be computed from the corresponding labels, without looking at the graph. The hub labeling (HL) algorithm received a lot of attention recently in both theoretical and experimental contexts. In particular, Cohen et al. (2003) developed an O(log n) approximation algorithm for finding the smallest labeling. Abraham at al. (2012) introduced a special kind of labeling hierarchical labeling (HHL) -- and showed that it is determined by an ordering of vertices. They give a practical algorithm to compute small HHLs on some classes of graphs, including road networks. Akiba et al. (2013) give a faster algorithm to compute the HHL from an order and apply it to social networks. We introduce a variant of the Cohen at al. algorithm that is faster both in theory and in practice. We also introduce on-line tie-breaking that reduces the label size on networks with multiple shortest paths, such as social networks. We introduce an algorithm to efficiently compute good orders. This algorithm scales to large networks and is more robust than the previous ones. Finally, we introduce a label compression technique that significantly reduces the size of the labels. Our experimental results show that the new HHL algorithm is practical on a much broader class of graphs. We also show that it usually produces labels that are not much bigger than those for the HL algorithm with the guaranteed approximation ratio.