General Term Indexing

UBGs are just one area of artificial intelligence where indexing can be used to improve efficiency. In general, any application dealing with large knowledge bases could benefit from indexing. Such applications include automated reasoning systems, symbolic computing systems, or term rewriting applications. In these applications, the knowledge bases can consist of first-order terms, clauses, or formulae. Parsing with TFSGs can be seen as a particular case of such applications.

Term indexing serves the purpose of rapidly retrieving candidate terms that satisfy a specific property. Formally, the term indexing problem can be formulated [Ramakrishnan et al.2001] as: Given a set of indexed terms $L$ and a binary relation (the retrieval condition, or indexing function) over terms $R$, for a query term t determine the subset $M\subset L$ such that $M=\{s \vert R(s,t) \downarrow \}$.

The following subsections outline various term indexing methods. The extensive presentations of term indexing found in [Ramakrishnan et al.2001] and [Graf1996] are used here as a guide.