Paper: Error-Tolerant Tree Matching

ACL ID C96-2145
Title Error-Tolerant Tree Matching
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1996

This paper presents an efficient algo- rithm for retrieving from a database of trees, all trees that match a given query tree appro,imately, that is, within a cer- tain error tolerance. It has natural lan- guage processing applications in search- ing for matches in example-based trans- lation systems, and retrieval from lexi- cal databases containing entries of com- plex feature structures. The algorithm has been implemented on SparcStations, and for large randomly generated syn- thetic tree databases (some having tens of thousands of trees) it can associatively search [or trees with a small error, in a matter of tenths of a second to few sec- onds.