next up previous
Next: Computational Complexity Up: Query Packs Previous: WAM Extensions


Using Query Packs

Figure 7 shows an algorithm that makes use of the pack execution mechanism to compute the result set $R$ as defined in our problem statement. The set $S$ of queries is here typically the set of all refinements of a given query, i.e., it does not correspond to the whole hypothesis space. From a query pack $\cal Q$ containing all queries in $S$, a derived pack ${\cal Q}'$ is constructed by adding a report_success/2 literal to each leaf of the pack; the (procedural) task of report_success(K,$i$) is simply to add $(K,i)$ to the result set $R$. Obviously a specific ILP system not interested in the result set itself could provide its own report_success/2 predicate and thus avoid the overhead of explicitly building the result set.1

Figure 7: Using query packs to compute the result set.
\begin{figure}
% latex2html id marker 386
\begin{tabbing}
xxx \= xxx \= xxx \= x...
...> evaluate\_pack($e$);\\
12 \> \> \} \\
13 \> \}
\end{tabbing}\par\end{figure}

Note that the algorithm in Figure 7 follows the strategy of running all queries for each single example before moving on to the next example: this could be called the ``examples in outer loop'' strategy, as opposed to the ``queries in outer loop'' strategy used by most ILP systems. The ``examples in outer loop'' strategy has important advantages when processing large data sets, mainly due to the ability to process them efficiently without having all data in main memory at the same time [22,6].


next up previous
Next: Computational Complexity Up: Query Packs Previous: WAM Extensions
Hendrik Blockeel 2002-02-26