## 4 Practice: Instance-Based Lower Bounds
### Experimental Results
Furthermore, note that our approach for a trivial graph with only 1 node yields the tight bound. However, we also clearly see that the quality of the lower bound deteriorates with bigger grids. The reason is probably that the average search space size grows linearly with the side length of the grid but Method A is quite inflexible concerning triple length and therefore seems to collect only roughly \(\log(\sqrt{n})\) triples. As real street networks are not structured exactly like lightheaded grids but exhibit grid-like structures as seen in the introduction, we conducted a final experiment on grids with almost uniform weights, see Table 3. On one hand, slightly perturbed weights seem more realistic and on the hand, we need unique shortest paths for the computation anyway. Interestingly, we observe that both the size of the computed lower bounds as well as the average search space develop in less extreme manners than for the experiments on the lightheaded grid. Consequently, the term \(\frac{LB}{|DSS|}\) develops in similar way as for the real \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **Test Graph** & \begin{tabular}{c} **Lower** \\ **Manhattan** \\ \end{tabular} & \begin{tabular}{c} **Bremen** \\ **(Fast Car)** \\ \end{tabular} & \
\begin{tabular}{c} **Bremen** \\ **(Car)** \\ \end{tabular} &
\begin{tabular}{c} **Bremen** \\ **(Highway)** \\ \end{tabular} \\ \hline \# nodes & 22 & 2828 & 40,426 & 119,989 & 1781 \\ \# edges (org) & 52 & 4020 & 64,663 & 227,567 & 1766 \\ \# edges (CH) & 77 & 7752 & 126,055 & 400,038 & 3340 \\ \(LB\)-construction space (A) & 5.5 MB & 233 MB & 40 GB & 354 GB & 84 MB \\ \(LB\)-construction space (B) & 4.9 MB & 8.8 MB & 91 MB & 328 MB & 6 MB \\ \(LB\)-construction time (A) & \textless{}1 s & 36 s & 100 m & 32.5 h & \textless{}1 s \\ \(LB\) (A) & 7.18 & 13.43 & 20.11 & 23.75 & 7.31 \\ \(LB\) (B) & 2.40 & 6.65 & 10.35 & 13.61 & 2.19 \\ \(|DSS|(avg.)\) & 10.27 & 29.85 & 61.99 & 78.34 & 7.58 \\ \(\frac{LB}{|DSS|}\) (A) & 0.699 & 0.449 & 0.324 & 0.303 & 0.964 \\ \(\frac{LB}{|DSS|}\) (B) & 0.233 & 0.222 & 0.166 & 0.173 & 0.288 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Experimental results. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Side Length** & **1** & **5** & **10** & **15** & **20** & **25** \\ \hline \(LB\) & 2.00 & 8.48 & 12.28 & 14.84 & 16.27 & 17.75 \\ \(|DSS|(avg.)\) & 2.00 & 12.48 & 32.94 & 53.21 & 77.2 & 102.88 \\ \(\frac{LB}{|DSS|}\) & 1.000 & 0.679 & 0.372 & 0.278 & 0.210 & 0.172 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Experimental results on lightheaded grid. world graphs. However, even though these perturbed grid graphs are not as awkward for the CH-heuristic to produce small average search spaces as their lightheaded counterparts, they still exhibit relatively big search spaces for a small number of nodes compared to our measured real-world networks. Moreover, we coincidentally observed that sea-routing implementations based on a globe discretization as mentioned in Section 3.1 exhibited significantly underwhelming performance of the CH-technique when compared to its speedup on street networks of similar size. This confirms the relevance of Theorem 1.