Chapter 8

Hub Labels

We now present a final optimization based on the Contraction Hierarchies method: hub labeling. This approach uses the precomputed CH structure to completely eliminate Dijkstra searches at query time, replacing them with fast memory lookups over precomputed hub labels.

Algorithm Description

In the contraction hierarchies method, each node maintains a label of reachable listings in the downward DAG. We extend this idea by computing a corresponding label in the upward DAG, which contains all hub vertices reachable from the query node within a maximum time budget $B$.

Here is an example of how the down labels can be computed in parallel

Here is an example of how a single up label can be computed

Once the hub labels have been precomputed, queries can be answered efficiently by intersecting the upward label of the query node with the downward labels of the hubs it reaches. This process leverages the triangle inequality and the cover property of hub labels, which guarantees that for any source-target pair, there exists at least one common hub on a shortest path between them.

and might look like this on a small example graph

Real World Implementations

An added benefit is that hub labels naturally fit relational databases— queries can be implemented using SQL JOIN operations.

Time Complexity

We assume we are given a contraction hierarchy and are now computing the hub labels from it.

In the worst case, the contraction hierarchy we get could be equivalent to the graph (e.g. a complete graph where all edges have weight 1). Then the construction of the hub labels will amount to running Dijkstra from every vertex on the entire graph, which yields a time complexity of $\mathcal{O}(V \cdot (V + E) \cdot \log V)$. As the worst case up label size is $V$ and the worst case down label size is $L$, we get a worst case query time of $\mathcal{O}(L \cdot V)$.

By contract for graphs with low highway dimension $h$ that are constructed using the methods from our previous chapter we compute (using our shortest path algorithm that runs in $\mathcal{O}((h \cdot \log h \cdot \log D)^2)$ time from the previous chapter)

• The up labels for each vertex in $\mathcal{O}(V \cdot (h \cdot \log h \cdot \log D)^2)$ time
• The down labels for each listing in $\mathcal{O}(L \cdot (h \cdot \log h \cdot \log D)^2)$ time

Which yields a combined $\mathcal{O}(V \cdot (h \cdot \log h \cdot \log D)^2)$ construction time. At query time, queries are answered by intersecting the up and down labels of the source and target nodes. As the maximum label size is $\mathcal{O}(h \cdot \log h \cdot \log D)$ [Abraham2016, page 16], the query time is $\mathcal{O}((h \cdot \log h \cdot \log D)^2)$ .

Space Complexity

In the worst case (e.g., a complete graph where all edges have weight 1), the storage complexity can be $\mathcal{O}(V^2)$, as every vertex stores all other vertices in its label.

For graphs with low highway dimension $h$ that are constructed using the methods from our previous chapter, the space required for hub labels is much lower. Each up label has size at most $\mathcal{O}(h \cdot \log h \cdot \log D)$ [Abraham2016, page 16]. Additionally we store each listing at up to $\mathcal{O}(h \cdot \log h \cdot \log D)$ hubs. This leads to a total space complexity of $\mathcal{O}(V \cdot h \cdot \log h \cdot \log D)$.

Empirical Results

While we do pay about a 2x price in setup time compared to contraction hierarchies, we get an approximate 3x speedup in query time.