Chapter 7

Contraction Hierarchies for Listing Queries

With a solid understanding of contraction hierarchies, we now explore how to adapt them for our specific problem: efficiently finding all listings reachable within a time budget. Recall that CH preprocesses the graph into two directed acyclic graphs (DAGs): the upward and downward graphs, with shortcut edges added during node contraction.

Algorithm Description

For a standard point-to-point shortest path, we perform a bidirectional Dijkstra: one forward search on the upward graph from the source and one backward search on the downward graph from the target.

In the listing query variant, our goal is to determine all listings reachable from a query point within a maximum time budget $B$. This is achieved by precomputing labels for each vertex in the upward DAG. Each label stores all listings that can be reached from that vertex via the downward DAG, constrained by the time budget.

Since each listing’s position is fixed, we can precompute the reachable listings from each vertex by traversing the downward graph in a time bounded search from each listing. This setup is embarrassingly parallel, as each listing's traversal can be computed independently.

Below is a small example to demonstrate the process.

After preprocessing, we perform a standard CH query. However, during traversal of the upward graph, we now accumulate results using each visited vertex’s precomputed label. This allows us to efficiently aggregate reachable listings.

This would work as follows on our small example graph starting from vertex C.

Time Complexity

Because we use a heuristic when constructing the contraction hierarchy, the theoretical bounds are not very exciting. Similarly to the full precompute method, the construction time is $\mathcal{O}(L \cdot (V + E) \cdot \log V)$, we run Dijkstra $L$ times. At query time we run another Dijkstra in $\mathcal{O}((V + E) \cdot \log V)$ time.

Suppose we have built a contraction hierarchy as described in the previous chapter, and the graph has a low highway dimension $h$. In this case, the time to compute labels is $\mathcal{O}(L \cdot (h \cdot \log h \cdot \log D)^2)$, where $L$ is the number of listings, $h$ is the highway dimension, and $D$ is the diameter of the graph. For a query, the time required is $\mathcal{O}((h \cdot \log h \cdot \log D)^2 + R^2)$, where $R$ is the number of listings returned by the query. The first term, $\mathcal{O}((h \cdot \log h \cdot \log D)^2)$, is the time to perform the shortest path search using the contraction hierarchy. The second term, $R^2$, accounts for the time needed to update or merge the result set as listings are found during the search. In summary: with low highway dimension and an appropriate contraction hierarchy, the time complexity is much more attractive.

Space Complexity

If we assume a worst case scenario and that the heuristic did not do a good job, then the storage complexity can be $\mathcal{O}(V \cdot L)$ in the worst case, i.e. we store all listings at all nodes, as in the full precompute approach.

Suppose we have built a contraction hierarchy as described earlier, and the graph has a low highway dimension $h$.

• Vertex storage: We need to store information for each vertex, which takes $\mathcal{O}(V)$ space.
• Label storage: For each listing (there are $L$ listings), we propagate its label through the contraction hierarchy. Due to the structure of the hierarchy, each label is stored at up to $\mathcal{O}((h \cdot \log h \cdot \log D)^2)$ vertices, where $D$ is the diameter of the graph.

Therefore, the overall space complexity is $\mathcal{O}(V + L \cdot (h \cdot \log h \cdot \log D)^2)$.

Empirical Performance

The empirical performance gains are substantial, despite relying on a heuristic for computing the contraction hierarchy. Preprocessing completes in seconds, not minutes, and query latency is negligible compared to network overheads.