The Treegram Index - An Efficient Technique for Retrieval in Linguistic Treebanks

In computational linguistics, large tree databases tagged with morpho-syntactic information are in need of fast retrieval of multiway tree structures. To tackle this problem, we present a generalization of the classical n-gram indexing technique called Treegram indexing. As an application of treegram indexing, we describe the Venona retrieval system, which handles the BH t treebank containing 508,650 phrase structure trees. 1 Tree Retrieval Multiway trees (MT, henceforth) play a central role in representing complex linguistic information because they are a common and well-understood data structure for describing hierarchical information. With the availability of large treebanks, retrieval techniques for highly structured data now become essential. One of the most well-known linguistic tree repositories is the Penn treebank of the University of Pennsylvania: Its fundament consists of a corpus containing 4.5 million words of American English; half of this corpus has been annotated for sk..