## 8 Experimental Evaluation on Repetitive Collections
\begin{table}
\begin{tabular}{l c c c c c c c} \hline \hline
**Collection** & **Text Size** & **Runs (\(\boldsymbol{r}/\boldsymbol{n}\))** & **CST size** & **RLCSA** & **(P)LCP** & **NPR** & **Total** \\ \hline Influenza & 148 & 0.019 & 27 & 0.77 & 0.21 & 0.42 & 1.40 \\ Para & 410 & 0.036 & 67 & 1.28 & 0.26 & 0.36 & 1.90 \\ Escherichia & 108 & 0.134 & 48 & 2.46 & 0.92 & 0.39 & 3.77 \\ Plain DNA & 50 & 0.632 & 61 & 5.91 & 3.62 & 0.29 & 9.82 \\ Einstein & 89 & 0.001 & 3 & 0.48 & 0.01 & 0.14 & 0.63 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Text size and size of our CST (which replaces the text), both in MB, and number of runs in \(\Psi\). On the right, bpc for the different components, and total bpc of the different collections considered. The NPR structure is the smallest setting between _RP-NPR_ and _RPBal-NPR_ for that particular text. Let us discuss the NPR operations now. We used a public Re-Pair compressor built by ourselves [50], which offers two alternatives when dealing with symbols of the same frequencies. The basic one, which we will call _RP-NPR_, stacks the pairs of the same frequency, whereas the second one, _RPBal-NPR_, enqueues them and obtains much more balanced grammars in practice. For our structure we tested values \(t=c=64,128,256,512\). We also include the basic regular RMM-tree of the previous sections (but running over our RLCSA and PLCP representations), to show that on repetitive collections our grammar-based version offers better space/time tradeoffs than the regular tree \(T_{m}\). For this version, _RP-RMM_, we used values \(L=36,64,128,256,512\). We measure the times of operations _NSV_ (as _PSV_ is symmetric) and _RMQ_ following the methodology of Section 6: We choose 10,000 random suffix tree leaves (corresponding to uniformly random suffix array intervals \([v_{l},v_{r}]=[v,v],v\in[1,n]\)) and navigate towards the root using operation \(\textit{Parent}(v_{l},v_{r})=[\textit{PSV}(v_{l}),\textit{NSV}(v_{r})-1]\). At each such node, we also measure the string depth, \(\textit{SDepth}(v_{l},v_{r})=\textit{LCP}[\textit{RMQ}(v_{l}+1,v_{r})]\). We average the times of the _NSV_ and _RMQ_ queries involved. Figure 11 shows the space/time performance of _RMM-NPR_, _RP-NPR_, and _RPBal-NPR_ on the repetitive collections. In addition, it shows the number of explicit accesses to _LCP_ made per NPR operation. In general the curves for total time and number of _LCP_ accesses have the same shape, showing that in practice the main cost of the NPR operations lies in retrieving the LCP values. In some cases, and most noticeably for _RMQ_ queries on Para using _RP-NPR_, using more space yields fewer _LCP_ accesses but higher time. This is because the Re-Pair grammars may be very unbalanced, and giving more space to them results in less tree pruning. Thus deeper trees, whose nodes have to be traversed one by one to cover short _LCP_ passages, are generated. _RPBal-NPR_ largely corrects this effect by generating more balanced grammar trees. Clearly, _RP-NPR_ and _RPBal-NPR_ dominate the space/time map for all queries. They always make better use of the space than the regular tree of _RMM-NPR_. _RPBal-NPR_ is usually better than _RP-NPR_, except on some particular cases, like _NSV_ on Escherichia, where _RP-NPR_ is faster. Figure 10: Evolution of the space, in bpc, of our structures for increasing prefixes of collections Influenza and Einstein. Figure 11: Space/Time performance of NPR operations. The \(x\)-axis shows the size of the NPR structure. On the left \(y\)-axis the average time per operation (solid lines), and on the right \(y\)-axis the average number of LCP accesses per operation (dashed lines). Note the log scale on \(y\) for Einstein. The times of our best variants are in the range of a few milliseconds per operation. This is high compared with the times obtained on general sequences. The closest comparison point is [PERSON] _et al_. 's CST [14] whose times are very similar, but it uses 4-6 bpc compared with our 1.4-1.9 bpc.