# Computing RF Tree Distance over Succinct Representations
## 5 Experimental Evaluation and Discussion
However, for the rf_nextsibling implementation, the running time difference seems to be much more insignificant than the difference observed for the rf_postorder implementation. These results are consistent with the theoretical analysis since in rf_nextsibling implementation, the number of times each operation is applied in the worst case is \((3n-3)\) and in the rf_postorder case it is \((5n-4)\). This concludes that the rf_nextsibling implementation provides better results for most trees when it is used to compute the distance for fully labelled trees. Let us consider now the trees obtained for real data, namely for _Salmonella_cgMLST data from EnteroBase (2018), with 391,208 strains and 3003 loci. We used two pairs of trees obtained for all strains by varying the number of loci being analyzed. Trees were generated using a custom highly parallelized version of the MSTree V2 algorithm (Mistree, 2018). One pair was fully labelled with 391,208 nodes in each tree, and the other pair was leaf labelled with 391,208 leaves. Both pairs represented the same data, they differed only in how data and inferred patterns were interpreted as trees. Figure 6 shows the memory allocation profile for rf_nextsibling implementation, which is similar for rf_postorder implementation, and for synthetic data. As observed in our previous analysis, for the first phase, the memory consumption is higher due to input parsing. In the second phase, the memory required for parsing is freed, and the memory  
Figure 8: Running time for trees with different sizes; (**a**) algorithm phase, and (**b**) parsing phase. Figure 9: Running time comparison for leaf labelled trees and fully labelled trees, (**a**) using NextSibling and FirstChild, and (**b**) using PostOrderSelect. consumption falls abruptly; in this phase, we have only the information stored in the two bit vectors and related data structures, and in the mapping that correlates the two trees. As discussed earlier, serializing and storing the trees and related permutations as their bit vector representations allow for us to avoid the memory excess required for parsing the Newick format. Table 2 presents the running time and memory usage for _Salmonella_ cgMLST trees. Figure 10 shows the memory allocation profile for rf_nextsibling implementation. We note that the Day algorithm supports only leaf labelled and unweighted trees; hence, we can only compare it for simple RF. Results for rf_postorder and rf_nextsibling are similar to those observed in synthetic data, with an almost linear increase with respect to both running time and memory usage. We observe that the number of tree nodes for RF and wRF tests is twice as much as those for weRF (a binary tree with 391,208 leaves has 782,415 the nodes in total). And that is reflected in running time and memory usage. As expected, for both synthetic and real data, both rf_nextsibling and rf_postorder implementations are slower than the Day algorithm implementation, because we have the overhead of using a succinct representation for trees. But it is noteworthy that those implementations offer a significant advantage in terms of memory usage, namely when trees are succinctly serialized and stored. This trade-off between memory usage and running time is common in this setting, with succinct data structures being of practical interest when dealing with large data. \begin{table}
\begin{tabular}{l c c c} \hline \hline
**Algorithm** & **Implementation** & **Time (s)** & **Memory Peak (MiB)** \\ \hline RF using the Day algorithm & rf\_day & 0.049 & 25.731 \\ RF using PostOrderSelect & rf\_postorder & 0.332 & 9.589 \\ RF using NextSibling and FirstChild & rf\_nextsibling & 0.319 & 9.567 \\ \hline wRF using PostOrderSelect & rf\_postorder & 0.356 & 18.362 \\ wRF using NextSibling and FirstChild & rf\_nextsibling & 0.340 & 18.339 \\ \hline weRF using PostOrderSelect & rf\_postorder & 0.192 & 11.668 \\ weRF using NextSibling and FirstChild & rf\_nextsibling & 0.185 & 11.658 \\ \hline \hline \end{tabular}
\end{table}