Building the Path Index

The indexing scheme used here is built on the same principles as the one described in Section 6.1, based on mother-daughter matching. The main difference is the content of the indexing keys, which now include a third element. This set is used in a two-layer indexing method.

In path indexing, each mother $M$ has its indexing scheme defined as: $\mathcal{L}(M)=\{(R_i,D_j,V_{i,j})\}$. The pair $(R_i,D_j)$ is the positional index key and represents the position $D_j$ in the rule $R_i$ of a matching daughter, while $V_{i,j}$ is a vector containing type values extracted from $M$. These vectors will be referred to as path index vectors. For each pair of mother-daughter that can unify, a different set of types is extracted. When $M$ is inserted in the chart as an edge, it is placed in the entry associated with $(R_i,D_j)$ as in the positional indexing method, but its vector $V_{i,j}$ accompanies $M$ in the chart.

The positional index uses the daughter's position as the index key, without any need for a function to compute the key during run-time. Path indexing, however, uses a two-layer method. The first layer consists of the positional key for daughters. The second layer uses types extracted from the typed feature structure. For this, each daughter is now associated with more than one index key. The set of a daughter's index keys is: $\mathcal{L}(D)=\{(R_i,D_j,V_{i,j})\}$, where $R_i$ is the rule number of a matching mother, $D_j$ is $D$'s position, and $V_{i,j}$ is the path index vector containing types extracted from $D$. A daughter $D$ has a different vector defined for each mother $M$ that can unify with $D$.