# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
These have complex travel time functions so linking and merging becomes more expensive. In addition, we switch from task based to loop based parallelization which is less effective. Measuring progress by \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{2}{c}{**CCH arcs**} & \multicolumn{2}{c}{**Expansions per arc**} & \multicolumn{2}{c}{**Index**} & \multicolumn{2}{c}{**Running Time [s]**} \\  & **[-10\({}^{3}\)]** & **Avg.** & **Max.** & =1 **[\%]** & **[GB]** & **Phase 1** & **Phase 2** \\ \hline Ber & 1977 & 1.039 & 31 & 98.6 & 0.09 & 1.5 & 6.2 \\ Ger06 & 22,519 & 1.075 & 44 & 98.4 & 1.06 & 30.1 & 21.6 \\ Ger17 & 31,488 & 1.090 & 107 & 98.5 & 1.50 & 35.0 & 107.4 \\ Eur17 & 114,857 & 1.099 & 115 & 98.4 & 5.47 & 189.6 & 557.0 \\ Eur20 & 128,921 & 1.191 & 109 & 96.9 & 6.32 & 209.6 & 1039.5 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Preprocessing statistics. Running times are for parallel execution with 16 cores. Figure 9: Average customization running times and parallelization efficiency (speedup/number of threads) on five customization runs of Eur20. The black bars (barely visible) indicate the standard deviation. The dashed line indicates running time with all parallelization code disabled. processed nodes (the for loop in Line 1 in Algorithm 5) or processed arcs (for loop on Line 2) is also insightful. However, for these, the correspondence is not linear. The last couple of thousand nodes and the last million arcs take almost half the total time. We observe that the choice of approximation parameters has a huge influence on running time and memory consumption. The best running time of around 1000 s is achieved with \(\beta=1000\) and \(\epsilon=1.0\) s. Thus, we use it as our default configuration. The worst running time is over six times higher. In the best configuration, we use only around 25 GB for travel time functions while a bad parameter choice or no approximation leads to crashes with out-of-memory errors. Generally, a larger \(\epsilon\) leads to looser approximation, lower travel time function complexity and thus less memory consumption. Conversely, a larger \(\beta\) causes the approximation to be executed less often and the memory consumption and function complexity increases. The average function complexity is usually well below \(\beta\) except for very small values of \(\epsilon\) or \(\beta\). In that case the complexity cannot be reduced sufficiently to keep the complexity below \(\beta\). If \(\beta\) is large, approximation is performed seldom and the influence of \(\epsilon\) becomes smaller. Similarly, when \(\epsilon\) is small, the influence of \(\beta\) is limited because the complexity cannot be reduced enough no matter how often approximation is performed. Clearly, the right choice of approximation parameters is essential to the performance of the preprocessing. When travel time functions are too complex, too much memory is used, and linking and merging are very expensive. However, when functions are approximated too loosely, a lot of time is spent in the reconstruction of exact functions for the times when bounds overlap. Thus, extreme parameter choice for \(\epsilon\) and \(\beta\) are detrimental to the running time, even though they may reduce memory consumption. Through all configurations, the memory usage peaks after around 60% of the triangles have been processed. The reason is the way we maintain travel time functions in memory during the customization. An arc's travel time function is stored once its lower ranked endpoint has been processed until its higher ranked endpoint has been processed. In the beginning, we process nodes with low rank and store many travel time functions. Only once we reach the higher ranked nodes do we start dropping a significant amount of the stored functions. This causes the observed peak. ### Queries

In this section, we investigate the performance of our query algorithms. Table 3 depicts the influence of the query optimizations. The basic approach does not achieve competitive running times.