Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    Multiway-Tree Retrieval Based on Treegrams

    Advances in Databases and Information Systems '97

    St Petersburg, 2nd - 5th September 1997


    H. Argenton & U. Güntzer


    Large tree databases as knowledge repositories become more and more important; a prominent example are the treebanks in computational linguistics: text corpora consisting of up to five million words tagged with syntactic information.

    Consequently, these large amounts of structured data pose the problem of fast tree retrieval: Given a database T of labeled multiway trees and a query tree q, find efficiently all trees t 2 T that contain q as subtree.

    This paper presents a generalization of the classical n-gram indexing technique for supporting fast retrieval of multiway tree structures: Treegram indexing covers database trees with subtrees of fixed height; each entry of the resulting index represents such a subtree together with the database trees that contain this subtree.

    The evaluation of a given query q preselects those database trees that contain all of q's cover trees and, in turn, tests these candidates rigorously for containment of q.

    As an application of treegram indexing, we describe the VENONA retrieval system, which handles the BHt treebank containing 508,650 phrase structure trees found in the morphosyntactical analysis of The Old Testament with altogether 3.3 million wordforms - results of a computational-linguistics project at the Ludwig-Maximilian's University of Munich.


    PDF filePDF Version of this Paper (175kb)