All Common Embedded Subtrees for Measuring Tree Similarity

Tree similarity measurement is key to tree-like data mining. In order to maximally capture common information between trees, we consider the problem of computing all common embedded subtrees, and advocate using the number/count of all common embedded subtrees as a measure of similarity. This problem is not trivial due to the inherent complexity of trees and the ensued large search space. The problem is theoretically analyzed and an effective algorithm for counting all common embedded subtrees is presented. Experimental evaluation shows that the all common embedded subtree similarity is very competitive against tree edit distance, in terms of both efficiency and effectiveness.