## 6 Comparing the CST Implementations
Indeed, our implementations based on _DAC_ and _DAC-Var_ are by far the fastest ones for these operations, 10 times faster than _CST-Sadakane_ and 100 to 1000 times faster than _FCST_. Even our slower implementations are way faster than _FCST_ and close to _CST-Sadakane_ times. Figure 4: _Cont_. Figure 5: Space/Time trade-off performance for operations _SLink_ and _LCA_. Note the log scale. _Child._ Figure 6 (right) shows operation _Child_, where we descend by a random child from the current node. Our times are significantly higher than for other operations, as expected, and the same happens to _CST-Sadakane_, which becomes comparable with our \"large and fast\" variants. _FCST_, on the other hand, is not much affected and becomes comparable with our \"small and slow\" variant. We note that, unlike other operations, the differences in performance depend markedly on the type of text. Figure 5: _Cont._  
Figure 6: Space/Time trade-off performance for operations _SDepth_ and _Child_. Note the log scale. Figure 7: Space/Time trade-off performance for operations _SDepth_ and _Child_. Note the log scale. _Letter._Figure 7 (left) shows operation \(\textit{Letter}(v,i)\), as a function of \(i\). This operation depends only on the CSA structure, and requires either applying \(i-1\) times \(\Psi\), or applying once \(A\) and \(A^{-1}\). The former choice is preferred for _FCST_ and the latter in _CST-Sadakane_. For our CST, using \(\Psi\) iteratively was better for these \(i\) values, as the alternative takes around 70 microseconds (recall we use [PERSON]'s CSA [12]). Figure 7: Space/Time trade-off performance for operation _Letter_ and for a full tree traversal. Note the log scale. A full traversal.Figure 7 (right) shows a basic suffix tree traversal algorithm: the classical one to detect the longest repetition in a text. This traverses all of the internal nodes using _FChild_ and _NSibling_ and reports the maximum _SDepth_. Although _CST-Sadakane_ takes advantage of locality, our \"large and fast\" variants are better while using half the space. Our \"small and slow\" variant, instead, requires a few hundred microseconds, as expected, yet _FCST_ has a special implementation for full traversals and it is competitive with our slow variant. \(\textit{LAQ}_{S}\) and \(\textit{LAQ}_{T}\).Figure 8 shows the performance of the operations \(\textit{LAQ}_{S}(v,d)\) and \(\textit{LAQ}_{T}(v,d)\). The times are presented as a function of parameter \(d\), where we use \(d=4,8,16,32,64\). We query the nodes visited over 10,000 traversals from a random leaf to the root (excluding the root). As expected, the performance of \(\textit{LAQ}_{S}\) is similar to that of _Parent_, and the performance of \(\textit{LAQ}_{T}\) is close to that of doing _Parent_\(d\) times. Note that, as we increase the value of \(d\), the times tend to a constant. This is because, as we increase \(d\), a greater number of queried nodes are themselves the answer to \(\textit{LAQ}_{S}\) or \(\textit{LAQ}_{T}\) queries. Figure 8: Space/Time trade-off performance for operation \(\textit{LAQ}_{S}(d)\) and \(\textit{LAQ}_{T}(d)\). Note the log scale. Figure 7: _Cont_. Discussion.The general conclusion is that our CST implementation does offer a relevant tradeoff between the two rather extreme existing variants. Our CSTs can operate within 8-12 bpc (that is, at most 50% larger than the plain byte-based representation of the text, and replacing it) while requiring a few hundred microseconds for most operations (the \"small and slow\" variants _Sad-Gon_ and _FMN-RRR_); or within 13-16 bpc and carrying out most operations within a few microseconds (the \"large and fast\" variants _DAC/DAC-Var_). In contrast, _FCST_ requires only 4-6 bpc (which is, remarkably, as little as half the space required by the plain text representation), but takes the order of milliseconds per operation; and _CST-Sadakane_ takes usually a few tens of microseconds per operation but requires 25-35 bpc, which is close to uncompressed suffix arrays (not to uncompressed suffix trees, though).