An Indexing Scheme for TFS Retrieval

Ninomiya et al. ninomiya02indexing propose an indexing method for typed feature structure retrieval engines. Given a database of TFSs, and a TFS query, the indexed retrieval engine selects a reduced number of TFSs for unification with the TFS query.

The index is built as a table with a row for each possible path in a TFS. The columns represent types (feature values). Each position (cell) indicated by a row $\pi$ and column $t$ in the table contains a list of TFSs from the database that have a type compatible with $t$ at the end of the path $\pi$. When a TFS query is given, the table entry for which a path is defined in the TFS query is selected, and the corresponding feature value is extracted from the TFS query. If there are more than one table entries that can be selected, the one containing the shortest list of TFSs is chosen. Only TFSs indicated by the matching list are selected for unification with the TFS query. Although the reported improvements in TFS retrieval times reach 37%, the costs of building such an index table could be prohibitive for TFSG parsing.