Paper: The Treegram Index-An Efficient Technique For Retrieval In Linguistic Treebanks

ACL ID E99-1041
Title The Treegram Index-An Efficient Technique For Retrieval In Linguistic Treebanks
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1999
Authors

2The employed algorithm is a generalization of the well-known transformation of trees to binary trees. d's value is a configurable parameter of the index- generation. Problem B VENONA uses only one tree- gram per node v: the treegram includ- ing every node found on the first h lev- els of the subtree rooted in v. This ap- proach keeps the index small but intro- duces another problem: A query treegram may not appear in the treegram index as it is. Therefore, VENONA expands all query treegram structures at runtime; for a given query treegram g, this expansion yields all database treegrams with a structure com- patible to g. That approach keeps the tree- gram index small and preserves efficiency. Problem C The evaluation of a given query q is processed along the following steps: (1) Accordin...