Tree-based indexing organizes the terms into a single tree. Each path into the tree represents common properties of the indexed terms, similar to decision trees or classification trees.
The basic tree-based indexing method is discrimination tree indexing. The tree reflects exactly the structure of terms. A more complex tree-based method is abstraction tree indexing. The nodes are labeled with lists of terms, in a manner that reflects the substitution of variables from a term to another: the domain of variable substitutions in a node is the codomain of the substitutions in a subnode (substitutions are mappings from variables to terms).
A relatively recent tree-based method was proposed in [Graf1995]: substitution tree indexing. This is an improved version of discrimination tree and abstraction tree indexing. Each path in the tree represents a chain of variable bindings. The retrieval of terms is based on a backtracking mechanism similar to the one in Prolog. Substitution tree indexing exhibits retrieval and deletion times faster than other tree-based indexing methods. However, it has the disadvantage of slow insertion times.
Since typed feature structures can be viewed as similar to first order terms with variables, the unification process requires a sequence of substitutions. Substitution tree indexing could be applied to TFSGs; unfortunately, published experimental results [Graf1995] indicating slow insertion times suggest that a method performing more efficient operations during run time is to be preferred. Future work will investigate possible adaptations of this technique to TFSG parsing.