# Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks +
## 2 Materials and Methods
### Shortcut Unpacking Data
Column \(|X|\) contains the number of times the shortest path changes during the day. Since the same path may be the fastest for several times, we also report the number of distinct paths in the last column. All values are arithmetic means over 1000 queries executed in bulk with source and target nodes drawn uniformly at random. ### Comparison with Related Work

Table 5 provides an overview over different techniques, their preprocessing and query times, space overhead of the index data structures and average query errors where approximation is used. Where possible, we obtained the code of competing algorithms (KaTCH: [[https://github.com/GVeitBatz/KaTCH](https://github.com/GVeitBatz/KaTCH)]([https://github.com/GVeitBatz/KaTCH](https://github.com/GVeitBatz/KaTCH)) (accessed on 15 March 2021); and TD-S: [[https://github.com/ben-strasser/td_p](https://github.com/ben-strasser/td_p)]([https://github.com/ben-strasser/td_p](https://github.com/ben-strasser/td_p)) (accessed on 15 March 2021 ) and evaluated them with same methodology, instances and queries as our algorithms. For other competitors, we report available numbers from the respective publications. In our comparison, KaTCH, heu SHARC, CFLAT and CATCHUp all achieve query times around 0.6 ms on Ger06. The original research implementation TCH reports slightly slower times than KaTCH. This may be because experiments were run on an older machine, but also because according to the KaTCH documentation, the newer query is somewhat more efficient. TCH pays for this speed with 4.7 GB index data. Reducing the KaTCH memory consumption while keeping exactness (ATCH) brings query times up to 1.24 ms. ATCH also feature a configuration where they only keep upper and lower bounds for each travel time function (ATCH \(\infty\)). This configuration uses even less memory than CATCHUp because the optimized order results in fewer shortcuts. However, query running times \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{2}{c}{**Preprocessing**} & \multicolumn{2}{c}{**Index**} & \multicolumn{2}{c}{**Query**} \\ \cline{2-7}  & **Time** & **Cores** & **Size** & **Time** & \multicolumn{2}{c}{**Rel. Error**} \\  & **[s]** & & **[GB]** & **[ms]** & **Avg. [\%]** & **Max. [\%]** \\ \hline TD-Dijkstra & - & - & - & - & 719.26 & - & - \\ TDCALT [4] & 540 & 1 & **0.23** & 5.36 & - & - \\ TDCALT-K1.15 [4] & 540 & 1 & **0.23** & 1.87 & 0.050 & 13.840 \\ eco L-SHARC [14] & 4680 & 1 & 1.03 & 6.31 & - & - \\ heu SHARC [14] & 12,360 & 1 & 0.64 & 0.69 & n/r & 0.610 \\ KaTCH & 169 & 16 & 4.66 & 0.64 & - & - \\ TCH [8] & 378 & 8 & 4.66 & 0.75 & - & - \\ ATCH (1.0) [8] & 378 & 8 & 1.12 & 1.24 & - & - \\ ATCH (\(\infty\)) [8] & 378 & 8 & 0.55 & 1.66 & - & - \\ inex. TCH (0.1) [8] & 378 & 8 & 1.34 & 0.70 & 0.020 & 0.100 \\ inex. TCH (1.0) [8] & 378 & 8 & 1.00 & 0.69 & 0.270 & 1.010 \\ TD-CRP (0.1) [9] & 289 & 16 & 0.78 & 1.92 & 0.050 & 0.250 \\ TD-CRP (1.0) [9] & 281 & 16 & 0.36 & 1.66 & 0.680 & 2.850 \\ FLAT [17] & 158,760 & 6 & 54.63 & 1.27 & 0.015 & n/r \\ CFLAT [17] & 104,220 & 6 & 34.63 & **0.58** & 0.008 & 0.918 \\ TD-S+9 & 542 & 1 & 3.61 & 2.07 & 0.001 & 1.523 \\
**CATCHUp** & **52** & 16 & 1.06 & 0.72 & - & - \\ \hline \multirow{5}{*}{Cond-1} & TD-Dijkstra & - & - & - & 814.60 & - & - \\ \cline{1-1}  & KaTCH & 859 & 16 & 42.81 & **1.26** & - & - \\ \cline{1-1}  & TD-S+9 & 601 & 1 & 5.28 & 2.61 & 0.001 & 0.963 \\ \cline{1-1}  & **CATCHUp** & **142** & 16 & **1.50** & 2.02 & - & - \\ \hline \multirow{5}{*}{Cond-2} & TD-Dijkstra & - & - & - & 2929.72 & - & - \\ \cline{1-1}  & KaTCH & 3066 & 16 & 146.97 & OOM & - & - \\ \cline{1-1}  & TD-S+9 & 3149 & 1 & 18.84 & **4.70** & 0.002 & 1.159 \\ \cline{1-1}  & **CATCHUp** & **747** & 16 & **5.47** & 4.92 & - & - \\ \hline \multirow{5}{*}{Cond-3} & TD-Dijkstra & - & - & - & 3784.11 & - & - \\ \cline{1-1}  & KaTCH & 7149 & 16 & 239.78 & OOM & - & - \\ \cline{1-1}  & TD-S+9 & 3352 & 1 & 20.65 & **4.23** & 0.006 & 1.733 \\ \cline{1-1}  & **CATCHUp** & **1249** & 16 & **6.32** & 5.60 & - & - \\ \hline \hline \end{tabular}
\end{table}