Efficient similarity measure for comparing tree structures

The problem of comparing tree structures is known to be a task often characterised by a particularly high computational complexity. Any attempt to reduce this complexity by considering a tree as a linear structure has generally resulted in a loss of information. Indeed, a comparison of tree structures (based on their similarity in order to classify them) which considers a tree as a single vector, obviously takes less execution time, but unfortunately has less credibility with respect to the classification task. The hierarchical relationships are thus ignored or suppressed and tree structures then behave like sequential data structures. The goal in this paper is to find a compromise between the processing time, on the one hand, and the preservation of information, on the other hand. For this purpose, the proposed approach relies on two types of traversal algorithm, namely the depth-first traversal and breadth-first traversal. The strategy aims to exploit the advantages of combining the two types of algorithms. To validate our approach, we conducted experiments on two sets of tree structures obtained from two collections of real and synthetic XML documents, respectively.