A sequence-based tree similarity search

Tree-structured data are pervasively growing and exploiting them based on similarity is essential for a broad number of applications. Therefore, there has been a growing need to develop high-performance techniques to efficiently look for similar trees across a large number of trees. To this end, in this paper, we present a new sequence-based approach for tree similarity search that exploits both the structural and the content characteristics of tree-structured data. In particular, we transform tree data into sequence representations using a modified Prüfer sequence that constructs a one-to-one mapping between tree data and their sequence representations. We introduce a new tree sequence distance based on the structural information of the data tree, which filters out a set of false positive candidates. We then introduce a refinement step exploiting the content information of data trees. The preliminary experimental results show that our algorithm achieves high performance. Our method is especially suitable for accelerating similarity computation in clustering and/or classification of large numbers of trees in massive datasets.