# Time-Dependent Alternative Route Planning: Theory and Practice +
## 3 The TDAG Algorithm
### Preprocessing Phase of Tdag
#### 3.1.1 Data Structure for Timestamped Predecessors  
The novelty of our succinct representation is the following: Rather than keeping a collection of trees per landmark, we maintain, for each pair \((\ell,v)\in L\times V\), two sequences of the same length:  
(i) \(\Delta_{\ell,v}\) is the sequence of sampled departure times from \(\ell\) to \(v\) (in increasing order), and (ii) \(\Pi_{\ell,v}\) is the sequence of predecessors of \(v\) in the corresponding \((\ell,v)\)-paths.  
All the departure times for \(\Delta_{\ell,v}\) are assumed to be integers from \(\{0,1,\ldots,86399\}\), considering an accuracy of seconds and a period of \(T=\) 86,400 s. Rather than using 3 bytes per cell, we exploit the fact that most departure times are smaller than \(2^{16}=\) 65,536 s. In particular, we keep an index \(h_{\ell,v}\) of the latest departure time in \(\Delta_{\ell,v}\), which is smaller than \(2^{16}\). The first \(h_{\ell,v}\) cells in \(\Delta_{\ell,v}\) store the absolute departure time values, but the remaining cells only store the offset of the actual departure times from the value \(2^{16}\). In this way, all the cells in \(\Delta_{\ell,v}\) require exactly 2 bytes. As for \(\Pi_{\ell,v}\), every cell is the relativeposition of the predecessor of \(v\), in its in-neighborhood list. One byte per cell is sufficient for real-world instances whose maximum in-degree is a small constant.  
A first observation of an initial implementation of this data structure was that a great deal of space was consumed for storing duplicates of exactly the same pairs of sequences for different landmark-destination pairs. For example, in the the continental-size EU instance with 18,010,173 nodes, for 16,000 landmarks, one would need to store 576,325,536,000 sequences. Nevertheless, we observed that there were only 1,632,168,375 _distinct_ sequences (1,623,701,331 departure time sequences and 8,467,044 predecessor sequences). To avoid this waste of space, we chose to store only pairs of (4-byte) pointers to sequences, among all landmark-destination pairs.  
After implementing this variant as well, we also observed that, in many cases, the same destination \(v^{*}\) had many repetitions of the same pairs of (4-byte) pointers to sequences, over all the landmarks. Indeed, this is quite reasonable for landmarks located towards the same direction and roughly at the same distance from \(v^{*}\). In order to avoid these repetitions of pairs of long pointers (8 bytes in total), we proceeded as follows (cf. Figure 2): We maintained a landmark-indexed dictionary \(Ldict_{v^{*}}\) per destination \(v^{*}\), whose value for a key \(\ell^{*}\in L\) is a pointer \(s^{*}\) to the cell of an array \(S_{v^{*}}\) containing a _unique_ pair \((p^{*},d^{*})\) of pointers to the sequences \(\Delta_{\ell^{*},p^{*}}\) and \(\Pi_{\ell^{*},p^{*}}\).  
The size \(|S_{v^{*}}|\) is exactly the number of _distinct_ pairs of pointers (to sequences) involving \(v^{*}\), among all landmarks and, on average, is significantly smaller than \(|L|\). Each cell of \(S_{v^{*}}\) requires 8 bytes. On the other hand, for \(Ldict_{v^{*}}\), we used bit-level representation of the stored values, with each cell consuming only \(\log_{2}(|S_{v^{*}}|+\mathit{indeg}(v^{*}))\) bits. Even for 16,000 landmarks, this was, at most, 14 bits per cell.  
Finally, we observed from real-world instances that, more often than not, a node \(v^{*}\) might always have the same predecessor, independently of landmarks and departure times. In those cases, rather than storing \(Ldict_{v^{*}}\) and \(S_{v^{*}}\), we simply stored this unique predecessor for \(v^{*}\).