# Computing RF Tree Distance over Succinct Representations
## 5 Experimental Evaluation and Discussion  
In this section, the performance of rf_postorder and rf_nextsibling implementations is discussed in comparison to their baselines and extensions. To evaluate the implementations, we used the ETE Python library to create a random generator of trees in the Newick format. To evaluate the RF distance, 10 trees (5 pairs) were generated, starting with 10,000 leaves and up to trees with 100,000 leaves, with a step of 10,000. Not only five pairs of trees were generated with information only on the leaves for all the sizes tested, but also fully labelled trees. We also considered in our evaluation the phylogenetic trees inferred from a real dataset from EnteroBase [22], namely _Salmonella_ core-genome MLST (cgMLST) data, with 391,208 strains and 3003 loci. To analyze the memory usage, the valgrind massit tool [31] was used. First, the memory used throughout the rf_postorder algorithm execution was analyzed for a tree that with 100,000 leaves. Figure 6 shows that for the first phase, the memory consumption is higher since a hash table has to be used to create the map that correlates labels and tree indexes. In the transition to the second phase, since the hash table is no longer needed and, as such, the memory it required is freed, the memory consumption falls abruptly. In the second phase of the algorithm, the memory consumption is lower since this phase only uses the information stored in the two bit vectors and related data structures, and in the mapping that correlates the two trees. We note that by serializing and storing the trees and related permutations as their bit vector representations, we can avoid the memory required for parsing the Newick format. Second, the memory usage for the second phase of rf_postorder and rf_day implementations was compared. Figure 7 shows the comparison between the two algorithms in terms of their memory peak usage. rf_postorder exhibits a significant lower memory peak compared to the rf_day algorithm. We note that the difference is smaller than expected in our theoretical analysis since in our implementations we are keeping track of common clusters, as described in Section 3.5, and extra space is required for supporting fast primitive operations over the bit vectors. If we omit that cluster tracking mechanism, we can reduce further the memory usage of our implementations. Then, the running time between the two algorithms was compared for the parse and algorithm phases; Figure 8. For the parse phase, we only compared rf_postorder with rf_day since rf_nextsibling has the exact same parsing phase as rf_postorder. It can be observed in Figure 8b that the differences between the running time of the two implementations are not significant, indicating similar performances between the two algorithms. In the second phase, a comparison was made between all three implementations. In Figure 8a, it can be observed that both rf_postorder and rf_nextsibling implementations presented almost the same results. Even though the theoretical complexity of those implementations is \(O(n\log(n))\), in practice, it seems to be almost linear. This finding suggests that the operations used to traverse the tree tend to be almost \(O(1)\) in practice even though they have a theoretical complexity of \(O(\log(n))\). The difference in the running time between these implementation and that of the rf_day one can be explained by the number of operations  
Figure 6: Heap allocation profile for two trees with 100,000 leaves in rf_postorder implementation. Figure 7: Memory usage peak comparison. that are computed for each node as explained previously, and because we used succinct tree representations. Next, the running time for RF and eRF distances was compared; Figure 9. We note that the Day algorithm does not support fully labelled trees. In both of the rf_postorder and rf_nextsibling implementations, the eRF distance seems to be also linear in practice.