Flexible Tree Matching
Ranjitha Kumar, Jerry O. Talton, Salman Ahmad, Tim Roughgarden, Scott R. Klemmer
Tree-matching problems arise in many computational domains, and several methods have been proposed for creating correspondences between labeled trees. By definition, tree-matching algorithms rigidly preserve ancestry: once two nodes have been placed in correspondence, their descendants must be matched as well. We introduce flexible tree matching, which relaxes this rigid requirement in favor of a tunable formulation in which the role of hierarchy can be controlled. Since flexible tree matching is strongly \NP-complete, we give a stochastic approximation algorithm for the problem, and demonstrate how the parameters of the model can be learned from a corpus of example matchings using structured prediction techniques. We also present results from applying the method to problems in Web design.