An interesting indexing method is proposed in [Penn and Popescu1997], employed for lexical generation (surface realization) in ALE [Carpenter and Penn2001]. An automaton-based index is used to extract words from the lexicon with descriptions matching a given typed feature structure.
A decision tree is built off-line, with nodes representing features and arcs representing types. The leaves of the tree point to lexical entries. The feature paths that are indexed are determined manually as paths that reach values bearing a semantic content. Each time a word is searched for by a feature structure, the indexing path is followed in the decision tree, and the reached leaf will give the desired lexical entry. Unfortunately, this method cannot be applied to parsing. In generation, the index can be entirely built off-line, since all paths in the feature structures representing lexical entries are fully accessible off-line. In parsing, it is not lexical entries that must be indexed, but categories in the grammar.