Flexible Tree Matching

Kumar, Ranjitha; Talton, Jerry O.; Ahmad, Salman; Roughgarden, Tim; Klemmer, Scott R.

doi:10.5591/978-1-57735-516-8/IJCAI11-445

Flexible Tree Matching

Ranjitha Kumar, Jerry O. Talton, Salman Ahmad, Tim Roughgarden, Scott R. Klemmer

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2674-2678.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-445

Abstract

Tree-matching problems arise in many computational domains. The literature provides several methods for creating correspondences between labeled trees; however, by definition, tree-matching algorithms rigidly preserve ancestry. That is, 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. We show that flexible tree matching is strongly NP-complete, give a stochastic approximation algorithm for the problem, and demonstrate how structured prediction techniques can learn the algorithm's parameters from a set of example matchings. Finally, we present results from applying the method to tasks in Web design.

Ranjitha Kumar, Jerry O. Talton, Salman Ahmad, Tim Roughgarden, and Scott R. Klemmer. 2011. Flexible Tree Matching. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2674–2678. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-445

@inproceedings{ijcai2011p445,
  title     = {Flexible Tree Matching},
  author    = {Kumar, Ranjitha and Talton, Jerry O. and Ahmad, Salman and Roughgarden, Tim and Klemmer, Scott R.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2674--2678},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-445},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-445},
}

TY  - CPAPER
TI  - Flexible Tree Matching
AU  - Kumar, Ranjitha
AU  - Talton, Jerry O.
AU  - Ahmad, Salman
AU  - Roughgarden, Tim
AU  - Klemmer, Scott R.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2674
EP  - 2678
DO  - 10.5591/978-1-57735-516-8/IJCAI11-445
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-445
ER  -