## 6 Comparing the CST Implementations  
We compare the following CST implementations: [PERSON] _et al._'s [PERSON] et al. (2010) implementation of [PERSON]'s compressed suffix tree [PERSON] et al. (2011) (_CST-Sadakane_); [PERSON]'s implementation of [PERSON] _et al._'s \"fully-compressed\" suffix tree [PERSON] et al. (2010) (_FCST_); and our best variants. These are called _Our CST_ in the plots. Depending on their _LCP_ representation, they are suffixed with _Sad-Gon_, _FMN-RRR_, _DAC_, and _DAC-Var_. We do not compare some operations like _Root_ and _Ancestor_ because they are trivial in all the implementations; _Locate_ and _Count_ because they depend only on the underlying CSA (which is mostly orthogonal, thus _Letter_ is sufficient to study it); _SLink\({}^{i}\)_ because it is usually better to do _SLink_\(i\) times; and _LAQ\({}_{S}\)_ and _LAQ\({}_{T}\)_ because they are not implemented in the alternative CSTs (these two are shown only for ours). We typically show space/time tradeoffs for all the structures, where the space is measured in bpc (recall that these CSTs replace the text, so this is the overall space required). The times are averaged \begin{table}
\begin{tabular}{l r r r r r r r r r} \hline \hline
**Collection** & **CSA bpc** & \multicolumn{6}{c}{**LCP bpc**} & \multicolumn{6}{c}{**RMM bpc**} & \multicolumn{2}{c}{**Total bpc**} \\ \cline{3-10}  & & _Sad-Gon_ & _FMN-RRR_ & _DAC_ & _DAC-Var_ & **Slow** & **Fast** & **Slow** & **Fast** \\ \hline dna & \(5.88\) & \(2.10\) & \(3.06\) & \(6.29\) & \(5.79\) & \(1.23\) & \(2.47\) & \(9.21\) & \(14.14\) \\ xml & \(4.47\) & \(2.10\) & \(2.03\) & \(9.30\) & \(7.77\) & \(1.23\) & \(2.47\) & \(7.73\) & \(14.71\) \\ proteins & \(7.91\) & \(2.10\) & \(2.59\) & \(7.43\) & \(6.97\) & \(1.23\) & \(2.47\) & \(11.24\) & \(17.35\) \\ sources & \(5.20\) & \(2.10\) & \(2.29\) & \(8.23\) & \(7.50\) & \(1.23\) & \(2.47\) & \(8.53\) & \(15.17\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Space breakdown of our compressed suffix tree. over a number of queries on random nodes. We use four types of node samplings, which make sense in different typical suffix tree traversal scenarios: (a) Collecting the nodes visited over 10,000 traversals from a random leaf to the root (used for _Parent_, _SDepth_, and _Child_ operations); (b) Same but keeping only nodes with at least 5 children (for _Letter_); (c) Collecting the nodes visited over 10,000 traversals from the parent of a random leaf towards the root via suffix links (used for _SLink_ and _TDepth_); and (d) Taking 10,000 random leaf pairs (for _LCA_). The standard deviation divided by the average is in the range [0.21, 2.56] for _CST-Sadakane_, [0.97, 2.68] for _FCST_, [0.65, 1.78] for _Our CST Sad-Gon_, [0.64, 2.50] for _Our CST FMN-RRR_, [0.59, 0.75] for _Our CST DAC_, and [0.63, 0.91] for _Our CST DAC-Var_. The standard deviation of the estimator is thus at most 1/100 th of that. Parent and _TDepth._Figure 4 shows the performance of operations _Parent_ and _TDepth_. As can be seen, _CST-Sadakane_ is about 5 to 10 times faster than our best results for _Parent_ and 100 times faster for _TDepth_. This is not surprising given that _CST-Sadakane_ stores the topology explicitly and thus these operations are among the easiest ones. In addition, our implementation computes _TDepth_ by brute force. Note, on the other hand, that _FCST_ is about 10 times slower than our slowest implementation. Figure 4: Space/Time trade-off performance for operations _Parent_ and _TDepth_. Note the log scale. _SLink_, _LCA_, and _SDepth_.Figure 5 shows the performance of operations _SLink_ and _LCA_, which are the ones most specific of suffix trees. Figure 6 (left) shows operation _SDepth_. Those operations happen to be among the most natural ones in [PERSON]'s _FCST_, which displays a better performance compared with the previous ones. _CST-Sadakane_, instead, is not anymore the fastest.