%\documentclass{article}
\documentclass[twoside,11pt]{article}
\usepackage{jair}
\usepackage{theapa}
\usepackage{subfigure}
%\usepackage{wrapfig}
\usepackage{epsfig}

\jairheading{16}{2002}{135-166}{7/01}{2/02}
\ShortHeadings{Improving the Efficiency of ILP through Query Packs}
{Blockeel, Dehaspe, Demoen, Janssens, Ramon, \& Vandecasteele}
\firstpageno{135}

\title{Improving the Efficiency of Inductive Logic Programming Through the
Use of Query Packs}
% \author{Hendrik Blockeel$^1$ \and Luc Dehaspe$^2$ \and Bart Demoen$^1$ \and 
% Gerda Janssens$^1$ \and Jan Ramon$^1$ \and Henk Vandecasteele$^2$ \and\\
% $^1$ Katholieke Universiteit Leuven, Department of Computer Science\\
% Celestijnenlaan 200A, B-3001 Leuven, Belgium\\
% $^2$ PharmaDM, Ambachtenlaan 54D, B-3001 Leuven, Belgium}

\author{\name Hendrik Blockeel \email hendrik.blockeel@cs.kuleuven.ac.be\\
\addr Katholieke Universiteit Leuven, Department of Computer Science\\
Celestijnenlaan 200A, B-3001 Leuven, Belgium
\AND
\name Luc Dehaspe \email luc.dehaspe@pharmadm.com\\
\addr PharmaDM, Ambachtenlaan 54D, B-3001 Leuven, Belgium
\AND
\name Bart Demoen \email bart.demoen@cs.kuleuven.ac.be\\
\name Gerda Janssens \email gerda.janssens@cs.kuleuven.ac.be\\
\name Jan Ramon \email jan.ramon@cs.kuleuven.ac.be\\
\addr Katholieke Universiteit Leuven, Department of Computer Science\\
Celestijnenlaan 200A, B-3001 Leuven, Belgium
\AND
\name Henk Vandecasteele \email henk.vandecasteele@pharmadm.com\\
\addr PharmaDM, Ambachtenlaan 54D, B-3001 Leuven, Belgium
}
%\usepackage{epsfig}

\newcommand{\comment}[1]{\begin{flushleft}{\tt *** {{#1}}}\end{flushleft}}
\newcommand{\Tilde}{{\sc Tilde}}
\newcommand{\Warmr}{{\sc Warmr}}
\newcommand{\ilProlog}{{\sc ilProlog}}
\newcommand{\MasterProLog}{{\sc MasterProLog}}
\newcommand{\Sicstus}{{\sc SICStus}}
\newcommand{\Apriori}{{\sc Apriori}}
\newcommand{\Progol}{{\sc Progol}}


\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
%\newenvironment{example}{{\bf Example}}{}


%% GJ comments %%%%
\newcommand{\gjbig  }[1]{ \[ \left[ \parbox{12cm}{{\sf GJ:}\\ #1}\right] \]   }
\newcommand{\gjsmall}[1]{ \batchmode\marginpar{\tiny (GJ): #1}\errorstopmode }

\renewcommand\baselinestretch{1}

\begin{document}

\maketitle

\begin{abstract}
Inductive logic programming, or relational learning, is a powerful
paradigm for machine learning or data mining.  However, in order for
ILP to become practically useful, the efficiency of ILP systems must
improve substantially. To this end, the notion of a query pack is
introduced: it structures sets of similar queries. Furthermore, a
mechanism is described for executing such query packs.  A complexity
analysis shows that considerable efficiency improvements can be
achieved through the use of this query pack execution mechanism. This
claim is supported by empirical results obtained by incorporating
support for query pack execution in two existing learning systems.
\end{abstract}

\section{Introduction}

Many data mining algorithms employ to some extent a generate-and-test
approach: large amounts of partial or complete hypotheses are
generated and evaluated during the data mining process.  This
evaluation usually involves testing the hypothesis on a large
data set, a process which is typically linear in the size of the data
set.  Examples of such data mining algorithms are {\sc Apriori}
\shortcite{Agrawal96:coll}, decision tree algorithms \shortcite{Quinlan93:other,Breiman84:other}, algorithms inducing decision rules \shortcite{Clark89:jrnl}, etc.

Even though the search through the hypothesis space is seldom
exhaustive in practical situations, and clever branch-and-bound or
greedy search strategies are employed, the number of hypotheses
generated and evaluated by these approaches may still be huge.  This
is especially true when a complex hypothesis space is used, as is
often the case in inductive logic programming (ILP), where the sheer
size of the hypothesis space is an important contribution 
%(though not the only one) 
to the high computational complexity of most ILP
approaches.  This computational complexity can be reduced, however,
by exploiting the fact that there are many similarities between hypotheses.

Most ILP systems build a hypothesis one clause at a time.  This search
for a single clause is what we will be concerned with in the rest of
this paper, and so the word ``hypothesis'' further on will usually
refer to a single clause.  The clause search space is typically
structured as a lattice.
%, and the search makes use of this lattice.
Because clauses close to one another in the lattice are similar, the
computations involved in evaluating them will be similar as well.
In other words, many of the computations that are performed when
evaluating one clause (which boils down to executing a query consisting of the
body of the clause) will have to be performed again when evaluating the
next clause.  Storing certain intermediate results during the
computation for later use could be a solution \shortcite<e.g., tabling as in
the XSB Prolog engine,>{Chen96:jrnl}, but may
% *** check XSB ref
be infeasible in practice because of its memory requirements.  It
becomes more feasible if the search is reorganised so that
intermediate results are always used shortly after they have been
computed; this can be achieved to some extent by rearranging the
computations.  The best way of removing the redundancy, however, seems to be to
re-implement the execution strategy of the queries in such a way that as much
computation as possible is effectively shared.

In this paper we discuss a strategy for executing sets of queries, 
organised in so-called query packs, that avoids the redundant 
computations.  The strategy is presented as an adaptation of the
standard Prolog execution mechanism.  The adapted execution mechanism
has been implemented in {\sc ilProlog}, a Prolog system dedicated to inductive
logic programming.
Several inductive logic programming systems have been re-implemented to make
use of this dedicated engine, and using these new implementations we
obtained experimental results showing in some cases a speed-up of more
than an order of magnitude.  Thus, our work significantly contributes
to the applicability of inductive logic programming to real world data
mining tasks.  In addition, we believe it may contribute to the state
of the art in query optimisation in relational databases.  Indeed, in
the latter field there has been a lot of work on the optimisation of
individual queries or relatively small sets of queries, but much less
on the optimisation of large groups of very similar queries, which
understandably did not get much attention before the advent of data
mining.  Optimisation of groups of queries for relational databases
seems an interesting research area now, and we believe techniques
similar to the ones proposed here might be relevant in that area.

The remainder of this paper is structured as follows.  In Section 2 we
precisely describe the ILP problem setting in which this work is set.
%set and point out some opportunities for efficiency improvements.  
In Section 3 we define the notion of a query pack and indicate how it
would be executed by a standard Prolog interpreter and what
computational redundancy this causes.  We further describe an
execution mechanism for query packs that makes it possible to avoid
the redundant computations that would arise if all queries in the pack
were run separately, and show how it can be implemented by making a
few small but significant extensions to the WAM, the standard Prolog
execution mechanism.  In Section 4 we describe how the query pack
execution strategy can be incorporated in two existing inductive logic
programming algorithms (\Tilde\ and \Warmr).  In Section 5 we present
experimental results that illustrate the speed-up that these systems
achieve by using the query pack execution mechanism.  In Section 6 we
discuss related work and in Section 7 we present conclusions and some
directions for future work.


\section{Inductive Logic Programming}

Inductive logic programming \shortcite{Muggleton94-JLP:jrnl} is situated in the
intersection of machine learning or data mining on the one hand,
and logic programming on the other hand.  It shares with the former
fields the goal of finding patterns in data, patterns that can be
used to build predictive models or to gain insight in the data.
With logic programming it shares the use of clausal first order logic as a 
representation language for both data and hypotheses.
In the remainder of this text we will use some basic notions from logic
programming, such as literals, conjunctive queries, and
variable substitutions.
%; for an introduction see \shortciteA{Lloyd87:other}.
We will use Prolog notation throughout the paper.  For an introduction
to Prolog and logic programming see \shortciteA{Bratko90:other}.

Inductive logic programming can be used for many different purposes, and
the problem statements found in ILP papers consequently vary.  
In this article we consider the so-called learning from interpretations
setting \shortcite{DeRaedt94-AI:jrnl,Deraedt97-AI:jrnl}.  It has been
argued elsewhere that this setting, while slightly less powerful than
the standard ILP setting (it has problems with, e.g., learning recursive
predicates), is sufficient for most practical purposes and scales up
better \shortcite{Blockeel99:jrnl}.   

We formulate the learning task in such a way that it
covers a number of different problem statements.  More specifically, we
consider the problem of detecting for a set of conjunctive
queries for which instantiations of certain variables each query
succeeds.  These variables are called {\em key variables}, and a grounding
substitution for them is called a {\em key instantiation}.  The intuition
is that an example in the learning task is uniquely identified by a single
key instantiation.

The link with ILP systems that learn clauses is then as follows.
The search performed by an ILP system is directed by
regularly evaluating candidate clauses.   Let us denote such a candidate
clause by $Head(X) \leftarrow Body(X,Y)$ where $X$ represents a vector
of variables appearing in the head of the clause and $Y$ represents 
additional variables that occur in the body.  We assume that the head
is a single literal and that a list of examples is given, where each
example is of the form $Head(X)\theta$ with $\theta$ a substitution that
grounds $X$.  Examples may be labelled (e.g., as positive or negative), but
this is not essential in our setting.  While an example can be
represented as a fact $Head(X)\theta$  when learning definite Horn 
clauses, we can also consider it just a tuple $X\theta$.  Both notations 
will be used in this paper.

Intuitively, when positive and negative examples are given, one wants to
find a clause that covers as many positive examples as possible, while
covering few or no negatives.  Whether a single example $Head(X)\theta$
is covered by the clause or not can be determined by running the query
$?- Body(X,Y)\theta$.  In other words, evaluating a clause boils down to
running a number of queries consisting of the body of the clause.
For simplicity of notation, we will often denote a conjunctive query
by just the conjunction (without the $?-$ symbol).

In some less typical ILP settings, the ILP algorithm does not search
for Horn clauses but rather for general clauses, e.g., {\sc Claudien}
\shortcite{DeRaedt97-ML:jrnl} or for frequent patterns that can be expressed
as conjunctive queries, e.g., \Warmr \shortcite{Dehaspe99:jrnl}.
These settings can be handled by our approach as well: all that is needed
is a mapping from hypotheses to queries that allow to evaluate these
hypotheses.  Such a mapping is defined by \shortciteA{DeRaedt97-ML:jrnl}
for {\sc Claudien}; for \Warmr\ it is trivial.



% The intuition behind this problem setting 
% is that given a set of examples and a set of conjunctions each of which
% describes a possible property, we want to know which properties hold for 
% which examples.

Given a set of queries $S$ and a set of examples $E$, the main task is
to determine which queries $Q \in S$ cover which examples $e \in E$.
We formalise this using the notion of a result set:

\begin{definition}[Result set]
  The {\em result set} of a set of queries S in a deductive database D
  for key $K$ and example set $E$, is 
\[RS(S,K,D,E) = \{ (K\theta,i) | Q_i \in S \mbox{ and } K\theta \in E \mbox{ and } Q_i\theta \mbox{ succeeds in }D\}\] 
\end{definition}

% We refer to the tuple $K$ as a {\em key}; the intuition behind this is that
% $K$ uniquely identifies a single example.  In the context of learning
% a single predicate the key would typically consist of the variables
% that occur in the head of the clause being learned.

Similar to the learning from interpretations setting defined in
\shortcite{Deraedt97-AI:jrnl}, the problem setting can now be stated as:
\begin{flushleft}
\noindent {\bf Given:} 
%\begin{itemize}
a set of conjunctive queries $S$, a deductive database $D$, a tuple $K$
of variables that occur in each query in S, and an example set $E$
%\end{itemize}

\smallskip

\noindent {\bf Find:} 
%\begin{itemize}
the result set $RS(S,K,D,E)$; i.e., find for each query $Q$ in $S$ those
ground instantiations $\theta$ of $K$ for which $K\theta \in E$ and $Q\theta$
succeeds in $D$.  
%\end{itemize}
\end{flushleft}

\begin{example}
Assume an ILP system learning a definition for {\tt grandfather/2}
wants to evaluate the following hypotheses:
\begin{verbatim}
      grandfather(X,Y) :- parent(X,Z), parent(Z,Y), male(X).
      grandfather(X,Y) :- parent(X,Z), parent(Z,Y), female(X).
\end{verbatim}

Examples are of the form {\tt grandfather($gf$,$gc$)} where $gf$ and
$gc$ are constants; hence each example is uniquely identified by a
ground substitution of the tuple $(X,Y)$.  So in the above problem
setting the set of Prolog queries S equals 
$\{(${\tt ?- parent(X,Z), parent(Z,Y), male(X)}$)$, $(${\tt ?- parent(X,Z), 
parent(Z,Y), female(X)}$) \}$
and the key $K$ equals $(X,Y)$.  Given a query $Q_i \in S$, finding all
tuples $(x,y)$ for which $((x,y), i) \in R$ (with $R$ the result set
as defined above) is equivalent to finding which of the {\tt
grandfather($x$,$y$)} facts in the example set are predicted by
the clause {\tt grandfather(X,Y) :- $Q_i$}.
\end{example}

The generality of our problem setting follows from the fact that once
it is known which queries succeed for which examples, the statistics
and heuristics that typical ILP systems use can be readily obtained
from this.  A few examples:

\begin{itemize}
\item discovery of frequent patterns
\shortcite{Dehaspe99:jrnl}: for each query $Q_i$ the
  number of key instantiations for which it succeeds just needs to be
  counted, i.e., $freq(Q_i) = |\{K\theta | (K\theta,i) \in R\}|$ with
  $R$ the result set.
\item induction of Horn clauses
  \shortcite{Muggleton95-NGC:jrnl,Quinlan93:proc}: the accuracy of a clause
  $H$ :- $Q_i$ (defined as the number of examples for which body and head
  hold, divided by the number of examples for which the body holds)
  can be computed as ${ |\{K\theta |
    (K\theta,i) \in R \land D \models H\theta\}| \over
    |\{K\theta | (K\theta,i) \in R\}|}$ with $R$ the result set.
\item induction of first order classification or regression trees
  \shortcite{Kramer96:proc,Blockeel98b:jrnl,Blockeel98:proc}: the class
  entropy or variance of the examples covered (or not covered) by a
  query can be computed from the probability distribution of the
  target variable; computing this distribution involves simple counts
  similar to the ones above.
\end{itemize}

After transforming the {\em grandfather/2} clauses into

\begin{verbatim}
      grandfather((X,Y)),I) :- parent(X,Z), parent(Z,Y), male(X), I = 1.
      grandfather((X,Y)),I) :- parent(X,Z), parent(Z,Y), female(X), I = 2.
\end{verbatim}
the result set can clearly be computed by collecting for all grounding $\theta$'s
where $K\theta \in E$ the answers to
the query {\tt ?- grandfather($K\theta$,I)} .
In Section \ref{querypacks} the queries will have a literal {\tt I = i} at the
end or another goal which by side-effects results in collecting the
result set.

In practice, it is natural to compute the result set using a double
loop: one over examples and one over queries and one has the choice as
to which is the outer loop.  Both the ``examples in outer loop'' and
the ``queries in outer loop'' have been used in data mining systems;
in the context of decision trees, see for instance
\shortciteA{Quinlan93:other} and \shortciteA{Mehta96:proc}.  We shall
see further that the redundancy removal approach we propose uses the
``examples in outer loop'' strategy. In both approaches however, given
a query and a key instantiation, we are interested only in whether the
query succeeds for that key instantiation.  This implies that after a
particular query has succeeded on an example, its execution can be
stopped.

In other words: computing the result set defined above 
boils down to evaluating each query on each example, where 
we are only interested in the existence of success for each such evaluation.
Computing more than one solution for one query on one example 
is unnecessary.

\section{Query Packs} \label{querypacks}

For simplicity, we make abstraction of the existence of keys in the following
examples.  What is relevant here, is that for each query we are only
interested in whether it succeeds or not, not in finding all answer 
substitutions.

Given the following set of queries
\begin{verbatim}
        p(X), I = 1.
        p(X), q(X,a), I = 2.
        p(X), q(X,b), I = 3.
        p(X), q(X,Y), t(X), I = 4.
        p(X), q(X,Y), t(X), r(Y,1), I = 5.
\end{verbatim}
we can choose to evaluate them separately. Since we are only
interested in one -- the first -- success for each query, we would
evaluate in Prolog the queries

\begin{verbatim}
        once((p(X), I = 1)).
        once((p(X), q(X,a), I = 2)).
        once((p(X), q(X,b), I = 3)).
        once((p(X), q(X,Y), t(X), I = 4)).
        once((p(X), q(X,Y), t(X), r(Y,1), I = 5)).
\end{verbatim}

The wrapper {\em once/1} is a pruning primitive and prevents the
unnecessary search for more solutions. Its definition in Prolog is
simply

\begin{verbatim}
        once(Goal) :- call(Goal), !.
\end{verbatim}


An alternative way to evaluate the queries consists in merging them
into one (nested) disjunction as in:

\begin{center}
\small
\tt p(X), (I=1 {\bf ;} q(X,a), I=2 {\bf ;} q(X,b), I=3 {\bf ;} q(X,Y), t(X), (I=4 {\bf ;} r(Y,1), I=5)).
\end{center}

The set of queries can now be evaluated as a whole: the success of
one branch in the disjunctive query corresponds to the success of the
corresponding individual query.

Compared to the evaluation of the individual queries, the disjunctive
query has both an advantage and a disadvantage:


\begin{itemize}
\item[ + ]
all the queries have the same prefix {\tt p(X)}, which is evaluated
once in {\bf each} individual query, while in the disjunctive query,
the goal {\tt p(X)} is evaluated only once; depending on the
evaluation cost of {\tt p/1}, this can lead to arbitrary performance gains.
\item[ $-$ ]
the usual Prolog pruning primitives are not powerful enough to prevent
all the unnecessary backtracking after a branch in the disjunctive
query has succeeded; this is explained further in Example \ref{example2}.
\end{itemize}

\begin{example} \label{example2}
In this example the literals $I = i$ have been left out,
because they do not contribute to the discussion:
\begin{verbatim}
      p(X), q(X).
      p(X), r(X).
\end{verbatim}
Evaluating these queries separately means evaluating
\begin{verbatim}
      once((p(X), q(X))).
      once((p(X), r(X))).
\end{verbatim}
or equivalently
\begin{verbatim}
      p(X), q(X), !.
      p(X), r(X), !.
\end{verbatim}
The corresponding disjunctive query is
\begin{verbatim}
      p(X), (q(X) ; r(X)).
\end{verbatim}

We can now try to place a pruning primitive in the disjunctive query:
{\tt !/0} at the end of each branch results in

\begin{verbatim}
      p(X), (q(X), ! ; r(X), !)
\end{verbatim}

The scope of the first cut is clearly too large: after the goal {\tt q(X)}
has succeeded, the cut will prevent entering the second branch. It
means that adding the cut in the disjunctive query leads to a wrong
result.

Using {\tt once/1} in the disjunctive query results in

\begin{verbatim}
      p(X), (once(q(X)) ; once(r(X)))
\end{verbatim}

This results in a correct query. However, both branches are still
executed for every binding that the goal {\tt p(X)} produces, even if both
branches have succeeded already.
\end{example}


The combination of the advantage of the disjunctive query with the
advantage of the individual query with pruning (once or cut) results in the
notion of the {\em query pack}. Syntactically, a query pack looks
like a disjunctive query where the {\em ;} control construct is
replaced by a new control construct denoted by {\em or}.  So the query
pack corresponding to the disjunctive query above is

\begin{center}
\small \tt 
p(X), (I=1 {\bf or} q(X,a), I=2 {\bf or} q(X,b), I=3 {\bf or} q(X,Y), t(X), (I=4 {\bf or} r(Y,1), I=5))
\end{center}

This query pack can be represented as the tree in Figure
\ref{querypack:fig}.  For a query pack $\cal Q$ such a tree has
literals or conjunctions of literals in the nodes.  Each path from the
root to a leaf node represents a conjunctive query $Q$ which is a {\em
member} of $\cal Q$, denoted $Q \in \cal Q$.  The {\em or} construct
is implicit in the branching points.

\begin{figure}[h]
\begin{center}
\epsfig{file=qpack.eps}
\caption{A query pack.}
\label{querypack:fig}
\end{center}
\end{figure}

The intended procedural behaviour of the {\em or} construct is that
once a branch has succeeded, it is effectively pruned away from the
pack during the evaluation of the query pack on the current example.
This pruning must be recursive, i.e., when all branches in a subtree of
the query pack have succeeded, the whole subtree must be pruned.
Evaluation of the query pack then terminates when all subtrees have
been pruned or all of the remaining queries fail for the example.

The semantics of the {\em or} construct and its efficient
implementation is the subject of the rest of this section.  It should
however be clear already now that in the case that all the answers of
each query are needed, pruning cannot be performed and the disjunctive
query is already sufficient, i.e., query packs are useful when a single
success per query suffices.







\subsection{Efficient Execution of Query Packs}

In Section \ref{meta-interpreter}, a meta-interpreter is given that
defines the behaviour of query packs. In practice this
meta-interpreter is not useful, because in many cases the
meta-interpreter itself causes more overhead than the use of query
packs can compensate for. Indeed, previously reported results
\shortcite{Demoen99:proc,Blockeel98:other} indicate that the overhead
involved in a high-level Prolog implementation destroys the efficiency
gain obtained by redundancy reduction. Moreover as discussed in
Section \ref{meta-interpreter}, the meta-interpreter does not have
the desired time-complexity. This shows that the desired procedural
semantics of {\em or} can be implemented in Prolog itself, but not
with the desired performance because Prolog lacks the appropriate
primitives.

The conclusion is that changes are needed at the level of the Prolog
engine itself. This requires an extension of the WAM (Warren Abstract
Machine) which is the underlying abstract machine for most Prolog
implementations.  The extended WAM provides the {\em or} operator as
discussed above: it permanently removes branches from the pack that
do not need to be investigated anymore.  This extended WAM has become
the basis of a new Prolog engine dedicated to inductive logic
programming, called {\sc ilProlog}.  This section continues with the
introduction of some basic terminology for query packs and explains at
a high level how query pack execution works.  Next our meta-interpreter
for the query pack execution is given and finally the changes needed
for the WAM are clarified.


\subsubsection{Principles of Query Packs (Execution)}

Before we discuss query pack execution in detail, note the following
two points: (1) during the pack execution, the pruning of a branch
must survive backtracking; (2) when executing a pack we are not
interested in any variable instantiations,
just in whether a member of the pack succeeds or not.  In
our previous description we were interested in the binding to the
variable {\tt I}. Since each branch can bind {\tt I} to only one value
-- the query number -- we collect these values in practice by a side
effect denoted in Section \ref{usingqp:sec} by {\em report\_success}.

% Before we discuss query pack execution in detail, note two points.
% It was explained above that cuts in the search tree should survive
% backtracking, except when the backtracking generates a new value for
% the key $K$; at that moment choice points should be restored.  The
% latter of course corresponds to the standard execution in Prolog.
% Therefore, without loss of generality we can ignore the special
% behaviour of the key in the pack execution mechanism; we just use the
% normal execution mechanism for the instantiation of the key and then
% execute the pack using the pack execution mechanism.  The answer set
% $AS$ is then obtained as follows: for each possible instantiation of
% the key $K$, the pack is executed with the key variable instantiated
% and success or failure of all its member queries is determined.

% A second point is that while adding a {\tt I=}$i$ literal at the end
% of a clause was useful for showing the equivalence of pack execution
% with separate execution of queries, in practice this extra literal is not
% necessary.  Instead, when a member query $i$ of the pack succeeds, the 
% execution mechanism can just set some flag $f[i]$ to true, at the same
% time it performs its cut (this will be done by the {\tt report\_success}
% predicate introduced further in this text).

% We give the algorithm in more detail in Section~\ref{usingqp:sec}.
% For now it is sufficient to understand two consequences of this
% approach: a) inside the pack execution cuts always survive
% backtracking; and b) we need to determine only success or failure of
% each member in the pack for a given key instantiation; i.e., no answer
% substitutions need be returned.

%\comment{opm: hier is ervan uitgegaan dat de key al geinstantieerd is;
%dit is enigszins inconsistent met het stuk hiervoor.}
%\gjbig{ is voor onze winkel niet echt van belang. wordt best toch vermeld}

The starting point for the query pack execution mechanism is the usual
Prolog execution of a query $Q$ given a Prolog program $P$.  By
backtracking Prolog will generate all the solutions for $Q$ by giving
the possible instantiations $\theta$ such that $Q \theta$ succeeds in
$P$.

%\comment{Misschien def. 1 meteen aanpassen aan wat hieronder staat?}
A query pack consists of a conjunction of literals and
a set of {\em alternatives}, where each alternative is again a query pack.
Note that leaves are query packs with an empty set of alternatives.
For each query pack ${\cal Q}$, $conj({\cal Q})$ denotes the
conjunction and $children({\cal Q})$ denotes the set of alternatives.
A set of queries is then represented by a so-called {\em root} query
pack.  For every query pack ${\cal Q}$, there is a path of query packs
starting from the root query pack ${\cal Q}_{root}$ and ending at the
query pack itself, namely $<{\cal Q}_{root}$ , ${\cal Q}_1$, ...,
${\cal Q}_{n}$, ${\cal Q}>$.  The query packs in this path are the
{\em predecessors} of ${\cal Q}$.  Every query pack has a set of {\em
dependent} queries, $dependent\_queries({\cal Q})$.  Let $<{\cal
Q}_{root}$ , ${\cal Q}_{i_1}$, ..., ${\cal Q}_{i_n}$, ${\cal Q}>$ be
the path to ${\cal Q}$, then $dependent\_queries({\cal Q})$ $=$ $\{
conj({\cal Q}_{root} ) \wedge conj({\cal Q}_{i_1}) \wedge \ldots
\wedge conj({\cal Q}_{i_n}) \wedge conj( {\cal Q}) \wedge conj({\cal
Q}_{j_1}) \wedge \ldots \wedge conj({\cal Q}_{j_m}) \wedge conj( {\cal
Q}_l)$ $ |$ $ <{\cal Q} , {\cal Q}_{j_1}$, ..., ${\cal Q}_{j_m}$,
${\cal Q}_l>$ is a path from $\cal Q$ to a leaf ${\cal Q}_l \}$.  Note that
$dependent\_queries({\cal Q}_{root})$ are actually the members of the
query pack as described earlier.

\begin{example}
For the query pack in Figure \ref{querypack:fig}, 
${\cal Q}_{root}$ is the root of the tree. 
$conj({\cal Q}_{root})$ is $p(X)$.
The set $children({\cal Q}_{root})$ contains the 4 query packs which
correspond to the trees rooted at the 4 sons of the root of the tree.
Suppose that these query packs are named (from left to right) 
${\cal Q}_{1}$, ${\cal Q}_{2}$, ${\cal Q}_{3}$,
and ${\cal Q}_{4}$.
Then $conj({\cal Q}_{2})$ equals $(q(X,a), I = 2)$, $children({\cal Q}_{2})$
equals the empty set, $conj({\cal Q}_{4})$ equals $(q(X,Y), t(X))$, and 
$dependent\_queries({\cal Q}_{4})$ equals $\{ (p(X), q(X,Y), t(X), I = 4)$,
$ (p(X), q(X,Y), t(X), r(Y,1), I = 5) \}$.

\end{example}

%Also note that for describing the execution of query packs the key of
%the query pack is not relevant and can be ignored in this context.
%\comment{opmerking over ``key not relevant'' verwijderd}

Execution of a root query pack ${\cal Q}_{root}$ aims at finding out
which queries of the set $dependent\_queries({\cal Q}_{root})$
succeed.  If a query pack is executed as if the {\em or}s were usual
disjunctions, backtracking occurs over queries that have already
succeeded and too many successes are detected.  To avoid this, it
should be the case that as soon as a query succeeds, the corresponding
part of the query pack should no longer be considered during
backtracking.  Our approach realises this by reporting success of
queries (and of query packs) to predecessors in the query pack.  A
(non-root) query pack ${\cal Q}$ can be safely removed if all the
queries that depend on it (i.e., all the queries in
$dependent\_queries({\cal Q})$) succeeded once.
%(namely all the queries that are below it in the query pack) have
%succeeded once. 
For a leaf ${\cal Q}$ (empty set of
children), success of $conj({\cal Q})$ is sufficient to remove it.
For a non-leaf ${\cal Q}$, we wait until all the
dependent queries report success or equivalently until all the query
packs in $children({\cal Q})$ report success.

At the start of the evaluation of a root query pack, the set of
children for every query pack in it contains all the alternatives in the
given query pack.  During the execution, query packs can be removed
from children sets and thus the values of the $children({\cal Q})$ change accordingly.
When due to backtracking a query pack is executed again, it
might be the case that fewer alternatives have to be considered.

The execution of a query pack ${\cal Q} \theta$ is defined by the algorithm
$execute\_qp( {\cal Q}, \theta)$ (Figure \ref{execpack:fig}) which imposes
additional control on the usual Prolog execution.

\begin{figure}
\begin{tabbing}
xxxx \= xxx \= x \= xxx \= x \= xxx\= x \= \kill
0 \> execute\_qp( pack ${\cal Q}$, substitution $\theta$) \{\\
1 \> while ( $\sigma$ $\leftarrow$ next\_solution( $conj({\cal Q})\theta$)\\
2 \> \> \{\\
3 \> \> \> for each ${\cal Q}_{child}$ in $children({\cal Q})$ do\\
4 \> \> \> \> \{\\
5 \> \> \>  \>  \> if ( execute\_qp( ${\cal Q}_{child}$ , $\sigma$) == success)\\
6 \> \> \>  \>  \> \> $children({\cal Q})$  $\leftarrow$  $children({\cal Q}) \setminus \{ {\cal Q}_{child}\}$\\ 
7 \> \> \> \> \}\\
8 \> \> \> if ( $children({\cal Q})$ is an empty set)  {\bf return(success)}\\
9 \> \> \}\\
10 \>{\bf return(fail)}\\
11\> \}\\
\end{tabbing}
\caption{The query pack execution algorithm.}
\label{execpack:fig}
\end{figure}

The usual Prolog execution and backtracking behaviour is modelled by
the while loop (line 1) which generates all possible solutions
$\sigma$ for the conjunction in the query pack.  If no more solutions
are found, fail is returned and backtracking will occur at the level
of the calling query pack.

The additional control manages the $children({\cal Q})$.
For each solution $\sigma$, the necessary children of ${\cal Q}$ will
be executed.
It is important to notice that the initial set of children of a query
pack is changed destructively during the execution of this algorithm.
Firstly, when a leaf is reached, success is returned (line 8) and the 
corresponding
child is removed from the query pack (line 6).
Secondly,  when a query pack that initially had several children, finally
ends up with an empty set of children (line 6), also this query pack is
removed (line 8).
The fact that children are destructively removed, implies that
when due to backtracking the same query pack is executed again for a
different $\sigma$, not all of the alternatives that were initially
there,
have to be executed any more. % hb: \\ weggelaten 
Moreover, by returning success the backtracking over the current query
pack conjunction $conj({\cal Q})$ is stopped: all branches have
reported success.

\subsubsection{A Meta-interpreter for Query Packs}
\label{meta-interpreter}

% \begin{figure}
% \begin{center}
% \input{flockaj.latex}
% \caption{ A graphical representation of an example query pack}
% \label{example-tree}
% \end{center}
% \end{figure}
The first implementation of the query pack execution algorithm is the
meta-interpreter
{\em meta\_execute\_qp(Q)}.
The meta-interpreter uses the following labelling in its representation
of a query pack:

\begin{itemize}
\item{\bf Query pack number}
        All the non-leaf query packs in the tree are numbered, depth first, from left to
        right $(qp(i))$.
\item{\bf Query number}
        Each leaf is numbered, from left to right. If the original 
        queries were numbered sequentially, then the numbers at
        the leaves correspond with these $( q(i))$.
\item{\bf Child number}
        For each non-leaf query pack with N children, all children 
        are numbered from 1 up to N sequentially $(ch(i))$.
\end{itemize}

Consider the query pack {\em a, (b, (c or d or e) or f or g,
(h or i or j))}.  
%A graphical representation is given in Figure \ref{example-tree}.  
Note that
the atoms in the example could in general be arbitrary 
conjunctions of non-ground terms.
Its labelling is shown in Figure
\ref{example-numbers}.
\begin{figure}
\begin{center}
%\input{flockajN.latex}
\epsfig{file=flockajN.eps}
\end{center}
\caption{Query pack numbers $qp(i)$, Query numbers $q(i)$ and Child numbers $ch(i)$ in our example.}
\label{example-numbers}
\end{figure}

A labelled query pack ${\cal Q}$ is then represented as a Prolog term
as follows (with ${\cal Q}_{f}$ the father of ${\cal Q}$):
\begin{itemize}
\item
        A leaf ${\cal Q}$ is represented by the term $(c, leaf(qpnbf,chnb,qnb))$
        with $c$ the $conj({\cal Q}) $, 
        $qpnbf$ the  query pack number of  ${\cal Q}_f$,
        $chnb$ the child number of ${\cal Q}$ w.r.t.  ${\cal Q}_f$,
        and $qnb$ the  query number of ${\cal Q}$.
\item
        A non-leaf ${\cal Q}$ is represented by the term $(c, or(cs,qpnbf,qpnb,chnb,totcs)$
        with $c$ the $conj({\cal Q}) $, 
        $cs$ the list $children({\cal Q})$, 
        $qpnbf$ the query pack number of  ${\cal Q}_{f}$,
        $qpnb$ the query pack number of  ${\cal Q}$,
        $chnb$ the child number of ${\cal Q}$ w.r.t.  ${\cal Q}_{f}$, 
        and $totcs$ the total number of $children({\cal Q})$).
        The query pack number of the father of the root query pack is assumed to be zero.
\end{itemize}

The example of Figure~\ref{example-numbers} has the following
representation (as a Prolog term):
\begin{small}
\begin{verbatim}
(a, or([(b,or([(c,leaf(2,1,1)),(d,leaf(2,2,2)),(e,leaf(2,3,3))],1,2,1,3)),
        (f,leaf(1,2,4)),
        (g,or([(h,leaf(3,1,5)),(i,leaf(3,2,6)),(j,leaf(3,3,7))],1,3,3,3))],
       0,1,1,3))
\end{verbatim}
\end{small}

During the execution of the meta-interpreter, {\tt solved/2} facts are
asserted. Each fact {\tt solved($qpnb$, $chnb$)} denotes that the
child with number $chnb$ from query pack with number $qpnb$ has
succeeded.  Such facts are asserted when reaching a leaf and also when
all children of a query pack have succeeded.  The meta-interpreter
only executes children for which no {\tt solved/2} fact has been
asserted.

Note that the time-complexity of this meta-interpreter is not yet as
desired. Execution of a query pack will always be dependent on the number of
original children, instead of the number of remaining (as yet
unsuccessful) children.


\begin{small}
\begin{tt}
\begin{tabbing}
hallo \= hallo \= \=\kill
run\_QueryPack(Q) :-\+ \\
        preprocess(Q, Qlabeled, 0, 1, 1, 1, \_, \_),\\
        \>     \% The code for preprocessing is given in Appendix A\\
        retractall(solved(\_, \_)),\\
        meta\_execute\_qp(Qlabeled),\\
        solved(0, \_), !.\-\\
\ \\
meta\_execute\_qp((A,B)) :- !, \+\\
        call(A),\\
        meta\_execute\_qp(B).\-\\
meta\_execute\_qp(or(Cs, QpNbF, QpNb, ChildNb, TotCs)) :- \+\\
        !,    \% 'or' corresponds to a non-leaf query pack\\
        handlechildren(Cs, QpNb, 1),\\
        all\_solved(QpNb, 0, TotCs),\\
        assert(solved(QpNbF,ChildNb)).\-\\
meta\_execute\_qp(leaf(QpNbF, ChildNb , QueryNb)) :- \+\\
        !, \% 'leaf' corresponds to the end of a query\\
        write(succeed(QueryNb)), nl,\\
        assert(solved(QpNbF,ChildNb)).\-\\
\ \\
handlechildren([], \_, \_).\\
handlechildren([C|\_], QpNb, ChildNb) :-\+\\
        not(solved(QpNb,ChildNb)), \\
        once(meta\_execute\_qp(C)), fail.\-\\
handlechildren([\_|Cs], QpNb, ChildNb) :-\+\\
        ChildNb1 is ChildNb + 1,\\
        handlechildren(Cs, QpNb, ChildNb1).\-\\
\ \\
all\_solved(QpNb, ChildNb, TotCs) :- \\
\>        (ChildNb = TotCs -> true \\
\>        ; \>  ChildNb1 is ChildNb + 1,\\
\>          \>  solved(QpNb, ChildNb1),\\
\>          \>  all\_solved(QpNb, ChildNb1, TotCs)\\
\>        ).\\
\end{tabbing}
\end{tt}
\end{small}


\subsubsection{WAM Extensions}

To fully exploit the potential of a query pack (shared computation and
avoidance of unnecessary backtracking) changes have to be made at the
level of the Prolog engine itself.  The explanation assumes a
WAM-based Prolog engine \shortcite{Ait-Kaci91:other}
%(a tutorial on the WAM can be found in \shortcite{Ait-Kaci91:other})
 but a short explanation of the execution of
disjunction in Prolog is given first, so that it becomes more easy to
see what was newly introduced in the WAM.

Assume that the body of a clause to be executed is {\em a, (b,c ; d ; e)}.
Assume also that all predicates have several clauses.
At the moment that execution has reached the first clause of $c$, the
choice point stack looks like Figure \ref{fig:wam1}: there are choice
points for the activation of $a$, the disjunction itself, $b$ and $c$. The
choice points are linked together so that backtracking can easily pop
the top most one. Each choice point contains a pointer to the next
alternative to be tried: only for the disjunction choice point, this
alternative pointer is shown. It points to the beginning of the second
branch of the disjunction. After all alternatives for $b$ and $c$ have
been exhausted, this second branch is entered and $d$ becomes active:
this is the situation shown in Figure \ref{fig:wam2}. At that point, the
alternative of the disjunction choice point refers to the last
alternative branch of the disjunction. Finally, once $e$ is entered, the
disjunction choice point is already popped.

\begin{figure}[h]
\begin{centering}
\subfigure[Choice points just after entering {\em c}.]{{\epsfig{file=wam1a.eps,width=.25\textwidth}} \label{fig:wam1}}
\subfigure[Choice points just after entering {\em d}.]{{\epsfig{file=wam1b.eps,width=.25\textwidth}} \label{fig:wam2}}
\subfigure[Choice points just after entering {\em e}.]{{\epsfig{file=wam1c.eps,width=.25\textwidth}} \label{fig:wam3}}
\caption{Illustration of execution of disjunction in the WAM.}
\label{fig:wamdisjunction}
\end{centering}
\end{figure}

When the goal $a$ produces a new solution, all branches of the
disjunction must be tried again. It is exactly this we want to avoid
for query packs: a branch that has succeeded once, should never be
re-entered. We therefore adapt the disjunction choice point to become
an {\em or}-choice point which is set up to point into a data structure
that contains references to each alternative in the {\em or}
disjunction. This data structure is named the {\em pack table}. Figure
\ref{fig:packwam1} shows the state of the execution when it has
reached $c$: it is similar to Figure \ref{fig:wam1}. The {\em or}-choice
point now contains the information that the first branch is being
executed.  As the execution proceeds, there are two possibilities:
either this first branch succeeds or it fails. We describe the
failing situation for the first branch and explain what happens on
success of the second branch. If the first branch has no solution,
backtracking updates the alternative in the {\em or}-choice point, to
point to the next branch in the pack table. The situation after the
second branch is entered is shown in \ref{fig:packwam2} and is again
similar to \ref{fig:wam2}. Suppose now that the branch with the goal $d$
succeeds: the entry in the pack table with {\em or}-alternatives is
now adapted by erasing the second alternative branch, backtracking
occurs, and the next alternative branch of the {\em or}-choice point
is taken. This is shown in \ref{fig:packwam3}.

When $a$ produces a new solution and the {\em or}-disjunction is entered
again, the pack table does no longer contain the second alternative branch
and it is never re-entered. The pack table is actually arranged in such a
way that entries are really removed instead of just erased so that
they cause no overhead later.

\begin{figure}[h]
\begin{centering}
\subfigure[The choice points just after entering {\em c}.]{{\epsfig{file=packwam1.eps,width=.28\textwidth}} \label{fig:packwam1}}
\subfigure[The choice points just after entering $d$ (the first branch did not succeed).]{{\epsfig{file=packwam2.eps,width=.28\textwidth}} \label{fig:packwam2}}
\subfigure[The choice points just after entering $e$ ({\em d} succeeded).]{{\epsfig{file=packwam3.eps,width=.28\textwidth}} \label{fig:packwam3}}
\caption{Illustration of execution of pack disjunction on the WAM.}
\label{fig:packwamdisjunction}
\end{centering}
\end{figure}

Two more issues must be explained: first, the pack table with alternatives
must be constructed at runtime every time the query pack is entered
for evaluation. This is done by emitting the necessary instructions in
the beginning of the code for the query pack. As an example, we show
the code for the query pack {\em a, (b,c or d or e)} in Figure
\ref{fig:packwamcode}.

\begin{figure}[h]
\begin{tabbing}
xxx \= xxx \= xxx \= xxx \= \kill
\>            \> construct\_pack\_table @1, @2, @3 \\
\>            \> call a \\
\>            \> query\_pack\_try \\
\> @1:        \> call b \\
\>            \> call c \\
\>            \> query\_pack\_prune \\
\> @2:        \> call d \\
\>            \> query\_pack\_prune \\
\> @3:        \> call e \\
\>            \> query\_pack\_prune \\
\end{tabbing}
\caption{Abstract machine code for {\em a, (b,c or d or e) }.}
\label{fig:packwamcode}
\end{figure}



Finally, in the example it is clear that at the moment that all
alternatives of an {\em or}-disjunction have succeeded, $a$ can stop
producing more solutions. So the computation can be stopped. In
general - with nested query packs - it means that one pack table entry of
the next higher {\em or}-node can be erased and this in a recursive way.
The recursive removal of entries from the pack tables, is done by the
instruction $query\_pack\_prune$.

We have implemented this schema in {\sc ilProlog}. Section 5 presents some
measurements in {\sc ilProlog}.


\subsection{Using Query Packs}
\label{usingqp:sec}

Figure \ref{usepacks:fig} 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 {\tt
  report\_success/2} literal to each leaf of the pack; the
(procedural) task of {\tt 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 {\tt report\_success/2}
predicate and thus avoid the overhead of explicitly building the
result set.\footnote{In our current implementation the result set is
  implemented as a bit-matrix indexed on queries and examples.  This
  implementation is practically feasible (on typical computers at the time of
  writing) even when the number of queries in the pack multiplied by
  the number of examples is up to a billion, a bound which holds for most
  current ILP applications.}

\begin{figure}[h]
\begin{tabbing}
xxx \= xxx \= xxx \= xxx \= \kill
%{\bf function} pack\_definition(pack P, key K) {\bf returns} clause:\\
%\>  P' := P;\\
%\>  $i$ := 1;\\
%\>  {\bf for each} leaf of P':\\
%\> \> add {\tt report\_success(K, $i$)} to the right of the conjunction in the leaf\\
%\> \> increment $i$  \\
%\>  {\bf return} (evaluate\_pack(N) :- current\_example(K), P');\\
%\>  {\bf return} (evaluate\_pack(K) :- P');\\
%\\
1 \> evaluate(set of examples $E$, pack ${\cal Q}$, key $K$) \{ \\
2 \> \>  ${\cal Q}' \leftarrow {\cal Q}$;\\
3 \> \>  $q \leftarrow 1$;\\
4 \> \>  {\bf for each} leaf of ${\cal Q}'$ {\bf do} \{ \\
5 \> \> \> add {\tt report\_success(K, $q$)} to the right of the conjunction in 
the leaf\\
6 \> \> \> increment $q$  \\
7 \> \> \} \\
8 \> \>  $C \leftarrow $ (evaluate\_pack($K$) :- ${\cal Q}'$);\\
9 \> \>  compile\_and\_load(C);\\
10 \> \>  {\bf for each} example $e$ in $E$ {\bf do} \{ \\ 
%11 \> \> \>    $k \leftarrow$ key($e$);\\
11 \> \> \>    evaluate\_pack($e$);\\
12 \> \> \} \\
13 \> \}
\end{tabbing}

\caption{Using query packs to compute the result set.}
\label{usepacks:fig}
\end{figure}

Note that the algorithm in Figure \ref{usepacks:fig} 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 \shortcite{Mehta96:proc,Blockeel99:jrnl}.

\subsection{Computational Complexity}

We estimate the speedup factor that can be achieved using query pack
execution in two steps: first we consider one-level packs, then we extend
the results towards deeper packs.

Lower and upper bounds on the speedup factor that can be achieved by
executing a one-level pack instead of separate queries can be obtained as
follows.  For a pack containing $n$ queries
$q_i = (a,b_i)$, let $T_i$ be the time needed to compute the first
answer substitution of $q_i$ if there are any, or to obtain failure
otherwise.  Let $t_i$ be the part of $T_i$ spent within $a$ and $t'_i$
the part of $T_i$ spent in $b_i$.  Then $T_s = \sum_i (t_i + t'_i)$
and $T_p = \max(t_i)+ \sum_i t'_i$ with $T_s$ representing
the total time needed for executing all queries separately and $T_p$ 
the total time needed for executing the pack.  Introducing $c = \sum_i t_i / 
  \sum_i t'_i$, which roughly represents the ratio of the computational
complexity in the shared part over that in the non-shared part, we have
\begin{equation}
\label{eq1}
{T_s \over T_p} = {\sum_i t_i + \sum_i t'_i \over \max_i t_i + \sum_i t'_i } = {c+1 \over { \max_i t_i \over \sum_i t'_i} + 1}
\end{equation}
Now defining $K$ as the ratio of the  maximal $t_i$ over the average $t_i$,
i.e. 
\[K = {\max_i t_i \over \sum_i t_i / n}\]
we can rewrite Equation~(\ref{eq1}) as
\begin{equation}
\label{eq2}
{T_s \over T_p} = {c + 1 \over {K \over n}c + 1}
\end{equation}
Since ${\sum_i t_i \over n} \leq \max t_i \leq \sum_i t_i$ we know
$1 \leq K \leq n$, which leads to the following bounds:
\begin{equation}
\label{eq3}
1 \leq {T_s \over T_p} \leq {c+1 \over {c \over n}+1} < \min(c+1,n)
\end{equation}
%When $n>>c$, $T_s/T_p$
%approximates $c+1$; when $c>>n$ it approximates $n$.  

Thus the speedup factor is bounded from above by the branching factor
$n$ and by the ratio $c$ of computational complexity in the shared
part over the computational complexity of the non-shared part; and
a maximal speedup can be attained when $\max t_i \simeq \sum t_i/n$
(or, $K \simeq 1$), in other words when the $t_i$ for all queries
are approximately equal.

For multi-level packs, we can estimate the efficiency gain as follows.
Given a query $q_i$, let $T_i$ be defined as above (the total time for
finding 1 answer to $q_i$ or obtaining failure).  Instead of $t_i$ and
$t'_i$, we now define $t_{i,l}$ as the time spent on level $l$ of the
pack when solving $q_i$; counting the root as level 0 and denoting the
depth of the pack with $d$ we have $T_i = \sum_{l=0}^d t_{i,l}$.
Further define $T_{i,l}$ as the time spent on level $l$ or deeper:
$T_{i,l} = \sum_{j=l}^d t_{i,j}$ with $d$ the depth of the pack.
(Thus $T_i = T_{i,0}$.).  We will assume a constant branching factor $b$
in the pack.  Finally, we define $\bar{t}_l = \sum_i
t_{i,l}/n$ with $n = b^d$.  For simplicity, in the formulae we
implicitly assume that $i$ always ranges from 1 to $n$ with $n$ the
number of queries, unless explicitly specified otherwise.  We then
have
\begin{equation}
\label{tp1:eq}
T_p = \max_i t_{i,0} + \sum_i T_{i,1} = \max_i t_{i,0} + \sum_{j=1}^b (\max_{i \in G_j} t_{i,1} + \sum_{i \in G_j} T_{i,2})
\end{equation}
where $j=1 \ldots b$ is the index of a child of the root and $G_j$ is
the set of indexes of the queries belonging to that child.  Now define
$K_0 = \max_i t_{i,0} / \bar{t}_0$ and define $K_1$ as the smallest
number such that $\max_{i \in G_j} t_{i,1} \leq K_1 \bar{t}_{j,1}$ with
$\bar{t}_{j,1} = \sum_{i \in G_j} t_{i,1} / b$.  Note $1 \leq K_0, K_1
\leq b$.  It then follows that
\begin{equation}
\sum_{j=1}^b \max_{i \in G_j} t_{i,1} \leq K_1 \sum_{j=1}^b \bar{t}_{j,1} = K_1 b \bar{t}_1
\end{equation}
which allows us to rewrite Equation (\ref{tp1:eq}) into
\begin{equation}
T_p \leq K_0 \bar{t}_0 + K_1 b \bar{t}_1 + \sum_i T_{i,2}
\end{equation}
where the equality holds if $\max_{i \in G_j} t_{i,1}$ is equal in all $G_j$.
The reasoning can be continued up till the lowest level of the pack,
yielding 
\begin{equation}
T_p \leq K_0 \bar{t}_0 + b K_1 \bar{t}_1 + b^2 K_2 \bar{t}_2 + \cdots
+ b^{d-1} K_{d-1} \bar{t}_{d-1} + \sum_i t_{i,d}
\end{equation}
and finally
\begin{equation}
T_p \leq K_0 \bar{t}_0 + b K_1 \bar{t}_1 + b^2 K_2 \bar{t}_2 + \cdots
+ b^{d-1} K_{d-1} \bar{t}_{d-1} + b^d \bar{t}_d
\end{equation}
with all $K_l$ between 1 and $b$.  We will further simplify the comparison
with $T_s$ by assuming $\forall l: K_l = 1$; the $K_l$ can then be dropped
and the inequality becomes an equality (because all maxima must be equal):
\begin{equation}
T_p = \bar{t}_0 + b \bar{t}_1 + b^2 \bar{t}_2 + \cdots + b^{d-1} 
\bar{t}_{d-1} + b^d \bar{t}_d
\end{equation}
% If we choose $K$ as the smallest number such that
% $\forall l: \max_i t_{i,l} \leq K \bar{t}_l$,
% then we get
% \[ \bar{t}_0 + b \bar{t}_1 + \cdots + b^d \bar{t}_d \leq T_p \leq K (\bar{t}_0 + b \bar{t}_1 + b^2 \bar{t}_2 + \cdots
% + b^{d-1} \bar{t}_{d-1}) + b^d \bar{t}_d\]

Note that for $T_s$ we have
\begin{equation} T_s = b^d \bar{t}_0 + b^d \bar{t}_1 + b^d \bar{t}_2 + \cdots + b^d \bar{t}_{d-1} + b^d \bar{t}_d
\end{equation}
It is clear, then, that the speedup will be
governed by how the $b^d \bar{t}_k$ terms compare to the $b^k
\bar{t}_k$ terms.  (In the worst case, where $K_k = b$, the latter
become $b^{k+1} \bar{t}_k$.)
We therefore introduce $R_{l,m}$ as follows:
\begin{equation}
R_{l,m} = {\sum_{k=l}^m b^m \bar{t}_k \over \sum_{k=l}^m b^k \bar{t}_k}
\end{equation}
The $R$ coefficients are always between 1 (if $\bar{t}_m$ dominates)
and $b^{m-l}$ (if $\bar{t}_l$ strongly dominates); for all $\bar{t}_l$
equal, $R_{l,m}$ is approximately $m-l$.

Further, similar to $c$ in our previous analysis, define 
\begin{equation}
c_l = {\sum_{k=0}^l b^k \bar{t}_k \over \sum_{k=l+1}^d b^k \bar{t}_k}
\end{equation}

Some algebra then gives
\begin{equation}
{T_s \over T_p} = {b^{d-l} c_l R_{0,l} + R_{l+1,d} \over c_l + 1}
\end{equation}
which needs to hold for all $l$.  We can interpret this as follows:
for a certain level $l$, $c_l$ roughly reflects the speedup gained by
the fact that the part up till level $l$ needs to be executed only 
once; the $R$ factors reflect the speedup obtained within these parts
because of the pack mechanism.

%We then have
%\[{T_s \over T_p} \geq {1 \over K} \cdot {b^{d-l} c_l + 1 \over c_l + 1} \]

This inequality holds for all $l$, hence we will find the best lower bound for
the speedup factor by maximizing the right hand side.  Note that $c_l$ 
increases and $b^{d-l}$ decreases monotonically with $l$.
It is clear that if at some point $c_l$ becomes much larger than 1, a 
speedup factor of roughly $b^{d-l}$ is obtained.  On the other hand, 
if $c_l$ is smaller than 1, then the behaviour of $b^{d-l} c_l$ is crucial.
Now, 
\[b^{d-l} c_l = {\bar{t}_l + {1 \over b} \bar{t}_{l-1} + \cdots + {1 \over
b^l} \bar{t}_0 \over \bar{t}_d + {1 \over b} \bar{t}_{d-1} + \cdots
+ {1 \over b^{d-l-1}} \bar{t}_{l+1}}.\]

Our conclusion is similar to that for the one-level pack.  If for some
$l$, $c_l>>1$, i.e., if in the upper part of the pack (up till level
$l$) computations take place that are so expensive that they dominate
all computations below level $l$ (even taking into account that the
latter are performed $b^{d-l}$ times more often), then a speedup of
$b^{d-l}$ can be expected.  If $c_l << 1$, which will usually be the
case for all $l$ except those near $d$, the speedup can roughly be
estimated as $\bar{t}_l / \bar{t}_d$.  The maximum of all these factors
will determine the actual speedup.

% Note that we simplified the analysis by assuming a constant branching
% factor of $b$.  If the branching factor higher up in the tree is
% greater, better speedups can be expected; otherwise the speedup will
% be worse.

% kan nu gewoon verdergezet worden op lagere levels
% uiteindelijk resultaat dan vergelijken met T_s waar b^{d-1} in voorkomt

%Under the assumption of a constant branching
%factor $b$, if the computation of literals at depth 1 to $i$ in the pack
%is dominant then the speedup factor approaches $b^{d-i}$ with
%$d$ the depth of the pack.



\section{Adapting ILP Algorithms to Use Query Packs}

In this section we discuss how the above execution method can be
included in ILP algorithms, and illustrate this in more detail for two
existing ILP algorithms.  Experimental results concerning actual
efficiency improvements this yields are presented in the next section.

\subsection{Refinement of a Single Rule}

Many systems for inductive logic programming use an algorithm that
consists of repeatedly refining clauses.  Any of these systems could
in principle be rewritten to make use of a query pack evaluation
mechanism and thus achieve a significant efficiency gain.  We first
show this for a concrete algorithm for decision tree induction,
then discuss the more general case.

\subsubsection{Induction of Decision Trees}

The first algorithm we discuss is \Tilde\ \shortcite{Blockeel98b:jrnl}, an
algorithm that builds first-order decision trees.  In a first-order
decision tree, nodes contain literals that together with the
conjunction of the literals in the nodes above this node (i.e., in a
path from the root to this node) form the query that is to be run for
an example to decide which subtree it should be sorted into.  When
building the tree, the literal (or conjunction of literals) to be
put in one node is chosen as
follows: given the query corresponding to a path from the root to this
node, generate all refinements of this query (a refinement of a query
is formed by adding one or more literals to the query); evaluate these
refinements on the relevant subset of the data,\footnote{I.e., 
that subset of the original data set for which the parent query
succeeded; or, in the decision tree context: the examples sorted into
the node that is being refined.} computing, e.g., the information gain
\shortcite{Quinlan93:other} yielded by the refinement; choose the best
refinement; and put the literals that were added to the original clause
to form this refinement in the node.

At this point it is clear that a lot of computational redundancy
exists if each refinement is evaluated separately.  Indeed all
refinements contain exactly the same literals except those added
during this single refinement step.  Organising all refinements into one
query pack, we obtain a query pack that essentially has only one 
level (the root immediately branches into leaves).
When \Tilde's lookahead facility is used \shortcite{Blockeel97:proc}, refinements
form a lattice and the query pack may contain multiple (though usually
few) levels.

Note that the root of these packs may consist of a conjunction of many
literals, giving the pack a broom-like form.  The more literals in the
root of the pack, the greater the benefit of query pack execution is
expected to be.


\begin{example}
  Assume the node currently being refined has the following query
  associated with it: {\tt ?- circle(A,C),leftof(A,C,D),above(A,D,E)},
  i.e., the node covers all examples $A$ where there is a circle to the
  left of some other object which is itself above yet another object.

The query pack generated for this refinement could for instance be

\epsfig{file=bongpack.eps}


When evaluating this pack, all backtracking through the root of the
pack (the ``stick'' of the broom) will happen only once, instead of
once for each refinement.  In other words: when evaluating queries one
by one, for each query the Prolog engine needs to search once again
for all objects $C$, $D$ and $E$ fulfilling the constraint {\tt
  circle(A,C), leftof(A,C,D), above(A,D,E)}; when executing a pack
this search is done only once.

\end{example}




\subsubsection{Other Algorithms Based on Rule Refinement}

As mentioned, any ILP algorithm that consists of repeatedly refining
clauses could in principle be rewritten to make use of a query pack
evaluation mechanism and thus achieve a significant efficiency gain.
Consider, e.g., a rule induction system performing an $A^*$ search
through a refinement lattice, such as \Progol\ 
\shortcite{Muggleton95-NGC:jrnl}.  Since $A^*$ imposes a certain order
in which clauses will be considered for refinement, it is hard to
reorganise the computation at this level.  However, when taking one
node in the list of open nodes and producing all its refinements, the
evaluation of the refinements involves executing all of them; this can
be replaced by a pack execution, in which case a positive efficiency
gain is guaranteed.  In principle one could also perform several
levels of refinement at this stage, adding all of the refinements to
$A^*$'s queue; part of the efficiency of $A^*$ is then lost, but the
pack execution mechanism is exploited to a larger extent.  Which of
these two effects is dominant will depend on the application: if most
of the first-level refinements would be further refined anyway at some
point during the search, clearly there will be a gain in executing a
two-level pack; otherwise there may be a loss of efficiency.  For
instance, if executing a two-level pack takes $x$ times as much time
as a one-level pack, it will bring an efficiency gain only if at least
$x$ of the first level refinements would afterwards be refined
themselves.

%\comment{trade-off tussen multi-level packs en A* kan misschien uitgewerkt
%worden.  bedenk: aantal queries stijgt maar gemiddelde evaluatietijd per
%query daalt!  bv. met 1s voor 1-level pack en 3s voor 2-level pack win je
%met 2-level pack van zodra je in A* minstens 3 knopen verder moet verfijnen.}


\subsection{Level-wise Frequent Pattern Discovery}

An alternative family of data mining algorithms scans the refinement
lattice in a breadth-first manner for queries whose frequency exceeds
some user-defined threshold.  The best-known instance of these
level-wise algorithms is the {\sc Apriori} method for finding frequent
item-sets \shortcite{Agrawal96:coll}.  \Warmr\ \shortcite{Dehaspe99:jrnl} is an
ILP variant of attribute-value based {\sc Apriori}.

Query packs in \Warmr\ correspond to hash-trees of item-sets in {\sc
  Apriori}: both are used to store a subgraph of the total refinement
lattice down to level $n$. The paths from the root down to level $n-1$
in that subgraph correspond to frequent patterns. The paths from root
to the leaves at depth $n$ correspond to candidates whose frequency
has to be computed. Like hash-trees in {\sc Apriori}, query packs in
\Warmr\ exploit massive similarity between candidates to make their
evaluation more efficient. Essentially the \Warmr\ algorithm starts
with an empty query pack and iterates between pack evaluation and pack
extension (see Figure~\ref{warmrpack:fig}). The latter is achieved by
adding all potentially frequent refinements\footnote{Refinements found
  to be specialisations of infrequent queries cannot be frequent
  themselves, and are pruned consequently.} of all leaves in the pack,
i.e., adding another level of the total refinement lattice.

\begin{figure}[t]
\epsfig{file=wpack.eps,width=\textwidth}
\caption{A sequence of 4 query packs in {\sc Warmr}. Refinement of the 
  above left query pack results in the 3-level pack above right.
  Removal of queries found infrequent during pack evaluation results in
  the bottom left pack.  Finally, another level is added in a second
  query expansion step to produce the bottom right pack. This
  iteration between expansion and evaluation continues until the pack
  is empty.}
\label{warmrpack:fig}
\end{figure}


\section{Experiments}

The goal of this experimental evaluation is to empirically investigate
the actual speedups that can be obtained by re-implementing ILP
systems so that they use the pack execution mechanism.  At this moment
such re-implementations exist for the \Tilde\ and \Warmr\ systems,
hence we have used these for our experiments.  These re-implementations
are available within the ACE data mining tool, available for academic
use upon request.\footnote{See {\tt http://www.cs.kuleuven.ac.be/\~{}dtai/ACE/.}}
We attempt to quantify (a) the speedup of packs w.r.t. to separate
execution of queries (thus validating our complexity analysis), and
(b) the total speedup that this can yield for an ILP system.

The data sets that we have used for our experiments are the following:
\begin{itemize}
\item The Mutagenesis data set : an ILP benchmark data set, introduced
  to the ILP community by \shortciteA{Srinivasan95:proc}, that consists of
  structural descriptions of 230 molecules that are to be classified
  as mutagenic or not.  Next to the standard Mutagenesis data set,
  we also consider versions of it where each example occurs $n$ times;
  this allows us to easily generate data sets of larger size where the
  average example and query complexity are constant and equal to those of
  the original data set.
\item Bongard data sets : introduced in ILP by
  \shortciteA{DeRaedt95-ALT:proc}, the so-called ``Bongard problems'' are a
  simplified version of problems used by \shortciteA{Bongard70:book}
  for research on pattern recognition.  A number of drawings are shown
  containing each a number of elementary geometrical figures; the drawings
  have to be classified according to relations that hold on the figures in
  them.  We use a Bongard problem generator to create data sets of varying
  size.
\end{itemize}


The experiments were run on SUN workstations: a Sparc Ultra-60
at 360 MHz for \Tilde, a Sparc Ultra-10 at 333 Mhz for \Warmr.
\Tilde\ and \Warmr\ were run with their default settings, except where
mentioned differently.

\subsection{Tilde}

%\subsubsection{Comparison of different implementations of Tilde}

We consider three different ways in which \Tilde\ can be run in
its \ilProlog\ implementation:

\begin{enumerate}
\item No packs: the normal implementation of \Tilde\ as described by
  \shortciteA{Blockeel98b:jrnl}, where queries are generated one by
  one and each is evaluated on all relevant examples.  Since
  queries are represented as terms, each evaluation of a query
  involves a meta-call in Prolog.
\item Disjoint execution of packs: a query pack is executed in which
  all queries in the pack are put beside one another; i.e., common
  parts are not shared by the queries.  The
  computational redundancy in executing such a pack is the same as that in
  executing all queries one after another; the main difference is that
  in this case all queries are compiled.
\item Packed execution of packs: a compiled query pack is executed where
  queries share as much as possible.
\end{enumerate}

The most interesting information is obtained by comparing (a) the
actual query evaluation time in settings 2 and 3: this gives a view of
the efficiency gain obtained by the removal of redundant computation
itself (we will abbreviate this as {\em exec} in the tables); and (b)
the total execution time in settings 1 and 3: this provides an
indication of how much is gained by implementing packs in an ILP system,
taking all other effects into account (re-implementation of the
computation of heuristics via a bit matrix, use of compiled queries
instead of meta-calls, etc.), or in other words: what the net effect
of the whole re-implementation is (indicated as {\em net} in the tables).

In a first experiment we used Bongard problems, varying (1) the size of the
data sets; (2) the complexity of the target hypothesis; and (3) \Tilde's
{\tt lookahead} parameter.  The complexity of the target hypothesis
can be small, medium, or none.  In the latter case the examples are
random, which causes \Tilde\ to grow ever larger trees in an attempt to
find a good hypothesis; the size of the final tree then typically depends 
on the size of the data set.  The lookahead parameter is used to control
the number of levels the pack contains; with lookahead $n$, packs of depth
$n+1$ are generated.

Table~\ref{sametrees:tab} gives an overview of results for the Bongard
problems.  The total induction time is reported, as well as (for
pack-based execution mechanisms) the time needed for pack compilation
and pack execution.  Note that the total time includes not only pack
compilation and execution, but also all other computations not directly
related to packs (e.g., the computation of heuristics from the bitmatrix).
The results can be interpreted as follows.

\begin{table}
\begin{center}
\begin{footnotesize}
\begin{tabular}{|c|c|c|ccc|ccc|cc|}
\hline
LA &  $bf$ & original &  \multicolumn{3}{c|}{disjoint} &  \multicolumn{3}{c|}{packed} & \multicolumn{2}{c|}{speedup}\\
&  &   &  total & comp & exec & total & comp & exec & \em net & \bf exec\\
\hline
\multicolumn{11}{c}{Simple target hypothesis}\\
\multicolumn{11}{c}{1007 examples}\\
\hline
0 & 16 & {\em 0.74} & {\em 0.62} & 0.14 & {\bf 0.13} & {\em 0.49} & 0.05 & {\bf 0.07} & {\em 1.51} & {\bf 1.86}\\ 
1 & 24 & {\em 2.44} & {\em 1.64} & 0.35 & {\bf 0.45} & {\em 1.09} & 0.14 & {\bf 0.11} & {\em 2.24} & {\bf 4.09}\\ 
2 & 18 & {\em 7.49} & {\em 4.07} & 0.8 & {\bf 1.57} & {\em 2.15} & 0.27 & {\bf 0.16} & {\em 3.48} & {\bf 9.81}\\ 
3 & 21  & {\em 29.9} & {\em 16.52} & 3.65 & {\bf 7.26} & {\em 7.18} & 1.26  & {\bf 0.28} & {\em 4.17} & {\bf 25.9}\\ 
\hline
\multicolumn{11}{c}{2473 examples}\\
\hline
0 & 16 & {\em 1.82} & {\em 1.43} & 0.17 & {\bf 0.34} & {\em 1.13} & 0.07 & {\bf 0.16} & {\em 1.61} & {\bf 2.13}\\ 
1 & 24 & {\em 5.72} & {\em 3.34} & 0.34 & {\bf 1.17} & {\em 2.24} & 0.11 & {\bf 0.3} & {\em 2.55} & {\bf 3.9}\\ 
2 & 18 & {\em 17.2} & {\em 8.45} & 0.78 & {\bf 3.95} & {\em 4.4} & 0.27 & {\bf 0.39} & {\em 3.92} & {\bf 10.1}\\ 
3 & 21 & {\em 69.8} & {\em 33.0} & 3.57 & {\bf 17.5} & {\em 13.7} & 1.13 & {\bf 0.69} & {\em 5.11} & {\bf 25.4}\\ 
\hline
\multicolumn{11}{c}{4981 examples}\\
\hline
0 & 19 & {\em 3.69} & {\em 2.72} & 0.29 & {\bf 0.67} & {\em 2.16} & 0.12 & {\bf 0.32} & {\em 1.71} & {\bf 2.09}\\ 
1 & 24 & {\em 11.4} & {\em 6.22} & 0.35 & {\bf 2.41} & {\em 4.17} & 0.13 & {\bf 0.63} & {\em 2.74} & {\bf 3.83}\\ 
2 & 18 & {\em 34.7} & {\em 16.0} & 0.74 & {\bf 8.14} & {\em 8.24} & 0.25 & {\bf 0.88} & {\em 4.21} & {\bf 9.25}\\ 
3 & 21 & {\em 142} & {\em 62.4} & 3.61 & {\bf 36.5} & {\em 24.9} & 1.09 & {\bf 1.45} & {\em 5.69} & {\bf 25.1}\\ 
\hline
\multicolumn{11}{c}{Medium complexity target hypothesis}\\
\multicolumn{11}{c}{1031 examples}\\
\hline
0 & 19 & {\em 1.01} & {\em 0.93} & 0.29 & {\bf 0.18} & {\em 0.66} & 0.11 & {\bf 0.07} & {\em 1.53} & {\bf 2.57}\\ 
1 & 21 & {\em 3.26} & {\em 2.8} & 0.98 & {\bf 0.56} & {\em 1.66} & 0.35 & {\bf 0.14} & {\em 1.96} & {\bf 4}\\ 
2 & 15 & {\em 6.36} & {\em 3.47} & 0.68 & {\bf 1.22} & {\em 1.95} & 0.25 & {\bf 0.15} & {\em 3.26} & {\bf 8.13}\\ 
3 & 18 & {\em 27.2} & {\em 14.6} & 3.75 & {\bf 5.75} & {\em 6.71} & 1.20  & {\bf 0.27} & {\em 4.06} & {\bf 21.3}\\ 
\hline
\multicolumn{11}{c}{2520 examples}\\
\hline
0 & 22 & {\em 3.16} & {\em 2.82} & 0.89 & {\bf 0.62} & {\em 1.91} & 0.3 & {\bf 0.24} & {\em 1.65} & {\bf 2.58}\\ 
1 & 24 & {\em 8.38} & {\em 5.88} & 1.5 & {\bf 1.86} & {\em 3.3} & 0.44 & {\bf 0.41} & {\em 2.54} & {\bf 4.54}\\ 
2 & 27 & {\em 38.5} & {\em 29.8} & 13.14 & {\bf 9.52} & {\em 10.3} & 2.44 & {\bf 0.6} & {\em 3.73} & {\bf 15.9}\\ 
3 &  18 & {\em 124} & {\em 58.02} & 10.3 & {\bf 28.6} & {\em 23.9} & 3.00  & {\bf 1.11} & {\em 5.21} & {\bf 25.7}\\ 
\hline
\multicolumn{11}{c}{5058 examples}\\
\hline
0 & 25 & {\em 6.35} & {\em 5.41} & 1.47 & {\bf 1.3} & {\em 3.73} & 0.56 & {\bf 0.53} & {\em 1.70} & {\bf 2.45}\\ 
1 & 24 & {\em 18.14} & {\em 12.98} & 3.2 & {\bf 4.15} & {\em 7.5} & 0.93 & {\bf 0.91} & {\em 2.42} & {\bf 4.56}\\ 
2 & 27 & {\em 119} & {\em 93.2} & 38.1 & {\bf 31.0} & {\em 35.3} & 9.09 & {\bf 1.7} & {\em 3.36} & {\bf 18.2}\\ 
3 & 27 & {\em 384} & {\em 275} & 108  & {\bf 89.1} & {\em 106} & 
25.9  & {\bf 2.83} & {\em 3.62} & {\bf 31.5}\\ 
\hline
\multicolumn{11}{c}{No target hypothesis}\\
\multicolumn{11}{c}{1194 examples}\\
\hline
0 & 28 & {\em 4.74} & {\em 6.65} & 3.34 & {\bf 0.94} & {\em 3.93} & 0.98 & {\bf 0.20} & {\em 1.21} & {\bf 4.70}\\ 
1 & 24 & {\em 16.32} & {\em 21.29} & 10.97 & {\bf 2.24} & {\em 11.65} & 3.41 & {\bf 0.31} & {\em 1.40} & {\bf 7.23}\\ 
2 & 24 & {\em 87.5} & {\em 130} & 82.3 & {\bf 13.8} & {\em 54.7} & 20.4 & {\bf 0.57} & {\em 1.60} & {\bf 24.1}\\ 
3 & 30 & {\em 373} & {\em 519} & 316  & {\bf 61.1} & {\em
220} & 74.9 & {\bf 1.34} & {\em 1.70} & {\bf 45.6}\\ 
\hline
\multicolumn{11}{c}{2986 examples}\\
\hline
0 & 31 & {\em 12.7} & {\em 16.5} & 7.04 & {\bf 2.68} & {\em 9.8} & 2.16 & {\bf 0.56} & {\em 1.30} & {\bf 4.79}\\ 
1 & 36 & {\em 65.1} & {\em 83.7} & 42.9 & {\bf 10.7} & {\em 42.47} & 11.2 & {\bf 1.14} & {\em 1.53} & {\bf 9.39}\\ 
2 & 33 & {\em 430} & {\em 606} & 396 & {\bf 84} & {\em 211.3} & 82.58 & {\bf 2.57} & {\em 2.03} & {\bf 32.6}\\ 
3 & 33 & {\em 1934} & {\em 2592} & 1610  & {\bf 375} & {\em 946} & 332  & {\bf 6.58} & {\em 2.04} & {\bf 57.0}\\ 
\hline
\multicolumn{11}{c}{6013 examples}\\
\hline
0 & 31 & {\em 25.3} & {\em 30.3} & 11.8 & {\bf 5.53} & {\em 18.3} & 3.53 & {\bf 1.27} & {\em 1.38} & {\bf 4.35}\\ 
1 & 39 & {\em 154} & {\em 198} & 91.2 & {\bf 33.4} & {\em 99.9} & 22.0 & {\bf 3.13} & {\em 1.54} & {\bf 10.7}\\ 
2 & 39 & {\em 1185} & {\em 1733} & 1076 & {\bf 358} & {\em 504} & 197 & {\bf 9} & {\em 2.35} & {\bf 39.8}\\ 
3 & 42 & {\em 4256} & {\em 6932} &  4441 & {\bf 1091} & {\em 2006} & 695 & {\bf 14.5} & {\em 2.12} & {\bf 75.4}\\
\hline
\end{tabular}
\end{footnotesize}
\end{center}
\caption{Timings of \Tilde\ runs on the Bongard data sets.  $LA$ = lookahead
setting; $bf$ = maximum
branching factor.  Reported times (in seconds) are the total time needed to
build a tree, and %for the disjoint/packed settings 
the time spent on  compilation respectively execution of packs.}
\label{sametrees:tab}
\end{table}

First of all, the table shows that significant speedups can be obtained
by using the pack mechanism; net speedups of over a factor 5.5 are obtained,
while the execution itself is up to 75 times faster compared to disjoint
execution.

A further observation is that for more complex target hypotheses greater
speedups are obtained.  This can be explained by the broom-like form of
the packs in \Tilde.  Complex target hypotheses correspond to deep trees,
and refinement of a node at a lower level of such a tree yields a pack
with a long clause before the branching, which in accordance with our
previous analysis should yield a speedup closer to the branching factor $b$
in the case of lookahead 0 (and more generally, closer to $b^{l+1}$ for
lookahead $l$, although the latter is much harder to achieve).
Note that the maximum branching factor occurring in each pack is included
in the table in column $bf$.

Finally, deeper packs also yield higher speedups, and this effect is larger
for more complex theories.  This is understandable considering the
following.  Let us call the clause that is being refined $c$.  With 
lookahead $l$, conjunctions of $l+1$ literals are added to the clause.
In some cases the first of these $l+1$ literals may fail immediately, which
causes this branch of the pack to have almost no execution time, while
cutting away $b^l$ queries.  Remember that according to our analysis, the 
speedup can in the limit approximate $b^l$ if the complexity of clause $c$ 
dominates over the complexity of the rest of the pack; 
such ``early failing branches'' in the pack cause the actual situation
to approximate closer this ideal case.


% Some interesting observations are:
% \begin{itemize}
% \item Comparing total times, net speedup factors of 1 to 4.7 are 
% obtained.  The speedup becomes larger when larger packs are generated
% (higher lookahead setting).
% \item Comparing execution times of disjoint and packed execution, speedup
% factors of 1.3 up to 23 are obtained.  Again, larger packs yield larger
% speedups.
% \item When subtracting the compilation time from the total induction time, 
% it can be seen that disjoint execution is approximately as fast as 
% the original implementation; i.e., the re-implementation from ``queries
% in outer loop'' to ``examples in outer loop'' does not have a net effect.
% Packed execution, of course, does yield an important gain.
% \item For each individual setting, the total induction time varies with the
% number of examples in the same way as for the other settings.  This confirms
% that the re-implementation does not affect the way in which the complexity
% of the learning algorithm depends on the number of examples.
% \end{itemize}

We have also run experiments on the Mutagenesis data set
(Table~\ref{muta:tab}), both in a regression and a classification
setting.  Here, query packs are much larger than for the Bongard data
set (there is a higher branching factor); with a lookahead of 2 the
largest packs had over 20000 queries.  For these large packs a
significant amount of time is spent compiling the pack, but even then
clear net speedups are obtained.\footnote{In one case, with a relatively
small pack, the system became slower.  The timings indicate that this is not
due to the compilation time, but to other changes in the implementation
which for this relatively simple problem were not compensated by the
faster execution of the packs.}  A comparison of execution times
turned out infeasible because in the disjoint execution setting the
pack structures consumed too much memory.

%   Such high
% speedups can be obtained in cases where occasionally a computationally
% complex clause is generated (with many variables and many literals
% sharing variables) and then refined; a large proportion of the total
% induction time may be spent for this, and it is exactly here that the
% highest speedup factor can be expected (high $c$ and $n$, see
% complexity analysis).



\begin{table}[t]
\begin{center}
\begin{tabular}{|c|c|ccc|ccc|cc|}
\hline
LA  &  original &  \multicolumn{3}{c|}{disjoint} &  \multicolumn{3}{c|}{packed} & \multicolumn{2}{c|}{speedup ratio}\\
      & &  total & comp & exec & total & comp & exec & {\em net} & {\bf exec} \\
\hline
\multicolumn{10}{c}{Regression, 230 examples}\\
\hline
% 0 & 12 & {\em 5.45} & {\em 7.84} & 2.71 & {\bf 3.04} & {\em 4.35} & 0.71 & {\bf 1.68} & {\em 1.25} & {\bf 1.81}\\ 
% 1 & 12 & {\em 22.71} & {\em 36.33} & 15.73 & {\bf 16.6} & {\em 12.18} & 4.0 & {\bf 4.85} & {\em 1.86} & {\bf 3.42}\\ 
% 2 & 13 & {\em 239.84} & {\em -- } & (99.87) & ({\bf 124.55}) & {\em 72.06} & 35.8 & {\bf 19.86} & {\em 3.33} & {\bf $>$6.27}\\ 
0 & {\em 31.5} & {\em 52.9} & 1.96 & {\bf 25.5} & {\em 45.5} & 1.02 & {\bf 19.25} & {\em 0.69} & {\bf 1.33}\\ 
1 & {\em 194.99} & {\em 248} & 55.9 & {\bf 109} & {\em 107} & 12.6 & {\bf 16.6} & {\em 1.82} & {\bf 6.53}\\ 
2 & {\em 2193} & -- & -- & -- & {\em 891} & 192 & {\bf 32.0} & {\em 2.46} & {\bf --}\\ 
\hline
\multicolumn{10}{c}{Classification, 230 examples}\\
\hline
% 0 & 18 & {\em 6.03} & {\em 9.04} & 2.98 & {\bf 4.05} & {\em 4.51} & 0.48 & {\bf 2.32} & {\em 1.34} & {\bf 1.75}\\ 
% 1 & 17 & {\em 28.38} & {\em 42.4} & 15.67 & {\bf 21.67} & {\em 13.6} & 2.36 & {\bf 7.38} & {\em 2.09} & {\bf 2.94}\\ 
% 2 & 24 & {\em 2453} & {\em -- } & (160.5) & ({\bf 397}) & {\em 124} & 39.29 & {\bf 39.8} & {\em 19.8} & {\bf $>$9.99}\\ 
0 & {\em 27.6} & {\em 27.3} & 1.83 & {\bf 4.71} & {\em 25.4} & 1.13 & {\bf 3.42} & {\em 1.09} & {\bf 1.38}\\ 
1 & {\em 38.02} & {\em 40.3} & 7.55 & {\bf 9.09} & {\em 30.6} & 3.11 & {\bf 3.65} & {\em 1.24} & {\bf 2.49}\\ 
2 & {\em 638} & -- & -- & -- & {\em 149} & 74.3 & {\bf 6.16} & {\em 4.2} & {\bf --}\\ 
\hline
\end{tabular}
\end{center}
\caption{Timings of \Tilde\ runs for Mutagenesis.  A $-$ in the table indicates that that
run ended prematurely.}
\label{muta:tab}
\end{table}


\subsection{Warmr}
%possible sentence
%For \Warmr a similar experiment has been done.
\subsubsection{Used Implementations}

For \Warmr\ we consider the following implementations:
\begin{enumerate}
\item No packs: the normal implementation of \Warmr, where queries are
  generated, and for all examples the queries are evaluated one by
  one.
\item With packs: An implementation where first all queries for one
  level are generated and put into a pack, and then this pack is
  evaluated on each example.
\end{enumerate}


\subsubsection{Datasets}

\paragraph{Mutagenesis}

We used the Mutagenesis dataset of 230 molecules,
where each example is repeated 10 times
to make more accurate timings possible and to have a better idea of 
the effect on larger datasets.
We used three different language biases.
{\tt 'small'} is a language bias that was chosen
so as to generate a limited number of refinements (i.e., a relatively
small branching factor in the search lattice); this allows us to
generate query packs that are relatively deep but narrow.
{\tt 'medium'} and {\tt 'large'} use broader but more shallow packs.
Table~\ref{tab:muta1:querycnt} summarises the number of  queries and
the number of frequent queries found for
each level in the different languages.

\begin{table}[t]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\multicolumn{7}{c}{Mutagenesis}\\
\hline Level & 
  \multicolumn{2}{c|}{\tt small} & 
  \multicolumn{2}{c|}{\tt medium} & 
  \multicolumn{2}{c|}{\tt large} \\
& Queries & Frequent& Queries & Frequent& Queries & Frequent \\\hline
1 &   8 &  5 &   37 &   26 &   45 &   31 \\ 
2 &  60 & 14 &  481 &   48 & 1071 &  211 \\
3 &  86 & 24 &  688 &  114 & 3874 & 1586 \\
4 & 132 & 31 &  699 &  253 &      &      \\
5 &  37 & 21 &  697 &  533 &      &      \\
6 &  29 & 18 & 1534 & 1149 &      &      \\
7 &  23 & 15 &  --  &  --  &      &      \\
8 &  17 & 12 &  --  &  --  &      &      \\
9 &   4 &  4 &  --  &  --  &      &      \\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:muta1:querycnt}Number of queries for the Mutagenesis experiment with \Warmr.}
\end{table}

\paragraph{Bongard}

We use Bongard-6013 for experiments with \Warmr{} as this system does not
construct a theory and hence the existence of a simple theory is not expected to
make much difference.

\subsubsection{Results}

In Tables \ref{tab:warmr_res_muta_small}, \ref{tab:warmr_res_muta_medium}
and \ref{tab:warmr_res_muta_large}
the execution times of \Warmr\ on Mutagenesis 
are given, with maximal search depth varying from 3 for the
large language to 9 levels for the small language.
Here, 'total' is the total execution time and 'exec' is the time needed
to test the queries against the examples.
In Table \ref{tab:warmr_res_bongard} 
the execution times of \Warmr\ on Bongard 
are given.

\begin{table}%[htb]
\begin{center}
\begin{tabular}{|c|cc|cc|cc|cc|}\hline
Level & 
\multicolumn{2}{c|}{No packs} &
\multicolumn{2}{c|}{With packs \ilProlog} & 
\multicolumn{2}{c|}{speedup ratio}\\
& total & exec & total & exec & \em net & \bf exec \\\hline
1&   0.35 & {\bf   0.23} &    0.18 & {\bf  0.15} & {\em  1.94} & {\bf  1.53} \\
2&   6.27 & {\bf   5.60} &    4.56 & {\bf  4.12} & {\em  1.38} & {\bf  1.36} \\
3&  36.93 & {\bf  31.49} &   14.01 & {\bf  9.87} & {\em  2.64} & {\bf  3.19} \\
4& 117.33 & {\bf  84.45} &   45.14 & {\bf 16.27} & {\em  2.60} & {\bf  5.19} \\
5& 215.95 & {\bf 104.36} &  129.37 & {\bf 20.78} & {\em  1.67} & {\bf  5.02} \\
6& 336.35 & {\bf 111.28} &  249.41 & {\bf 22.39} & {\em  1.35} & {\bf  4.97} \\
7& 569.14 & {\bf 115.80} &  497.86 & {\bf 24.63} & {\em  1.14} & {\bf  4.70} \\
8& 902.72 & {\bf 120.99} &  831.30 & {\bf 25.98} & {\em  1.09} & {\bf  4.66} \\
9&1268.16 & {\bf 119.60} & 1148.23 & {\bf 32.28} & {\em  1.10} & {\bf  3.71} \\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:warmr_res_muta_small}Results for \Warmr\ on the
Mutagenesis dataset using a small language.}
\end{table}

\begin{table}%[htb]
\begin{center}
\begin{tabular}{|c|cc|cc|cc|cc|}\hline
Level & 
\multicolumn{2}{c|}{No packs} &
\multicolumn{2}{c|}{With packs \ilProlog} & 
\multicolumn{2}{c|}{speedup ratio}\\
& total & exec & total & exec & \em net & \bf exec \\\hline
1&    2.58 &{\bf   2.27}&    2.16 &{\bf   2.09} &{\em  1.19} &{\bf 1.09} \\
2&  112.98 &{\bf  42.32}&   34.35 &{\bf  13.39} &{\em  3.29} &{\bf 3.16} \\
3&  735.19 &{\bf 128.67}&  262.83 &{\bf  34.70} &{\em  2.80} &{\bf 3.71} \\
4& 4162.15 &{\bf 287.72}& 1476.06 &{\bf  54.10} &{\em  2.82} &{\bf 5.32} \\
5&17476.98 &{\bf 444.44}& 6870.16 &{\bf  73.11} &{\em  2.54} &{\bf 6.08} \\
6&65138.72 &{\bf 866.85}&25921.73 &{\bf 104.81} &{\em  2.51} &{\bf 8.27} \\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:warmr_res_muta_medium}Results for \Warmr\ on the
Mutagenesis dataset using a medium language.}
\end{table}

\begin{table}%[htb]
\begin{center}
\begin{tabular}{|c|cc|cc|cc|cc|}\hline
Level & 
\multicolumn{2}{c|}{No packs} &
\multicolumn{2}{c|}{With packs \ilProlog} & 
\multicolumn{2}{c|}{speedup ratio}\\
& total & exec & total & exec & \em net & \bf exec \\\hline
1&    2.82 &{\bf    2.42}&    2.28 &{\bf   2.11}&{\em 1.24} &{\bf  1.15} \\
2&  408.85 &{\bf  102.38}&  102.29 &{\bf  50.67}&{\em 4.00} &{\bf  2.02} \\
3&27054.33 &{\bf 1417.76}& 3380.19 &{\bf 370.44}&{\em 8.00} &{\bf  3.83} \\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:warmr_res_muta_large}Results for \Warmr\ on the
Mutagenesis dataset using a large language.}
\end{table}

\begin{table}%[htb]
\begin{center}
\begin{tabular}{|c|cc|cc|cc|cc|}\hline
Level & 
\multicolumn{2}{c|}{No packs} &
\multicolumn{2}{c|}{With packs \ilProlog} & 
\multicolumn{2}{c|}{speedup ratio}\\
& total & exec & total & exec & \em net & \bf exec \\\hline
 1&  0.24 & {\bf  0.22} &   0.24 & {\bf  0.23} & {\em  1.00} & {\bf  0.96} \\
 2&  0.83 & {\bf  0.75} &   0.77 & {\bf  0.68} & {\em  1.08} & {\bf  1.10} \\
 3&  3.28 & {\bf  2.82} &   2.34 & {\bf  1.92} & {\em  1.40} & {\bf  1.47} \\
 4& 11.56 & {\bf  9.31} &   6.08 & {\bf  4.28} & {\em  1.90} & {\bf  2.18} \\
 5& 38.34 & {\bf 28.11} &  16.20 & {\bf  8.15} & {\em  2.37} & {\bf  3.45} \\
 6& 75.51 & {\bf 46.97} &  36.57 & {\bf 12.22} & {\em  2.06} & {\bf  3.84} \\
 7&135.64 & {\bf 71.60} &  68.96 & {\bf 15.59} & {\em  1.97} & {\bf  4.59} \\
 8&186.23 & {\bf 84.93} & 102.46 & {\bf 17.82} & {\em  1.82} & {\bf  4.77} \\
 9&210.82 & {\bf 88.97} & 120.76 & {\bf 18.52} & {\em  1.75} & {\bf  4.80} \\
10&216.61 & {\bf 89.38} & 125.84 & {\bf 18.88} & {\em  1.72} & {\bf  4.73} \\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:warmr_res_bongard}\Warmr\ results on Bongard.}
\end{table}

\subsubsection{Discussion}

The execution time of \Warmr{} 
has a large component that is not used to evaluate queries. 
This is caused by the fact that \Warmr{} needs to do a lot of administrative
work.  In particular,
theta-subsumption tests should be done on the 
queries to check wether a query is equivalent to another candidate, or if
a query is a specialisation of an infrequent one.
In the propositional case (the \Apriori\ algorithm), these tests are very 
simple, but in the first order case they require exponential time in the 
size of the queries.  Of course, when using larger datasets, the relative
contribution of these administrative costs will decrease proportionally.
It can be observed that at deeper levels, these costs are less for the 
setting using packs.  One of the causes is the fact that the no-packs version 
also uses more memory than the packs setting (and hence causes proportionally 
more memory management).

Here again, the most important numbers are the speedup factors for the 
execution of queries.  
Speedup factors of query execution do not always increase with
increasing depth of the packs, 
in contrast to \Tilde\ where larger packs yielded higher speedups.  
At first sight we found this surprising; however it becomes
less so when the following observation is made.  When refining a pack
into a new pack by adding a level, \Warmr\ prunes away branches that
lead only to infrequent queries.  There are thus two effects when
adding a level to a pack: one is the widening of the pack at the
lowest level (at least on the first few levels, a new pack typically
has more leaves than the previous one), the second is the narrowing of
the pack as a whole (because of pruning).  Since the speedup obtained
by using packs largely depends on the branching factor of the
pack,
speedup factors can be expected to decrease when the narrowing effect
is stronger than the widening-at-the-bottom effect.  
This can be seen, e.g, in the small-mutagenesis experiment, where at the 
deepest levels queries are becoming less frequent.  For the mutagenesis 
experiment with the medium size language, query execution speedup factors 
are larger as the number of queries increases much faster.
For the mutagenesis experiment with the large language, it is the total
speedup that is large, as the language generates so many queries that the most
time-consuming part becomes the administration and storage in memory.
The packs version is much faster as it stores the queries in trees, requiring
significantly less memory.

\subsection{Comparison with Other Engines}

Implementing a new special-purpose Prolog engine, different from the
already existing ones, carries a risk: given the level of
sophistication of popular Prolog engines, it is useful to check whether
the new engine performs comparably with these existing engines, at least
for the tasks under consideration here.  The efficiency gain obtained
through query pack execution should not be offset by a less efficient
implementation of the engine itself.

Originally the \Tilde\ and \Warmr\ systems were implemented in
\MasterProLog.  In an attempt to allow them to run on other platforms,
parts of these systems were re-implemented into a kind of ``generic''
Prolog from which implementations for specific Prolog engines
(\Sicstus, \ilProlog) can easily be derived (the low level of
standardisation of Prolog made this necessary).  Given this situation,
there are two questions to be answered: (a) does the move from
\MasterProLog\ to other Prolog engines influence performance in a
negative way; and (b) does the performance loss, if any, reduce the
performance improvements due to the use of packs?  

\Tilde\ and \Warmr\ have been tuned for fast execution on \MasterProLog\
and \ilProlog\ but not for \Sicstus, which makes a comparison with the
latter unfair; therefore we just report on the former 2 engines.
Table~\ref{engines:tab} shows some results.  These confirm that \ilProlog\
is competitive with state-of-the-art Prolog engines.

% \footnote{Note that
%   possible performance degradation should not necessarily be
%   attributed to the engine itself; a specific program may be tuned for
%   efficiency on a specific engine; when ported to a different engine
%   its performance typically decreases unless it is re-tuned for the
%   new engine.}

% Since \ilProlog\ is a new Prolog engine, we wanted to compare its
% performance
% \gjsmall{hier Master Prolog weg en eventueel ook Sicstus...}
% with existing engines; obviously the efficiency gain achieved through
% the query pack execution it offers should not be offset by a less
% efficient implementation of the engine itself.

\begin{table}%[t]
\begin{center}
\begin{tabular}{|lc|ccc|}
\hline
Data set & LA & \small \MasterProLog\ & \small \ilProlog (original)\ & \small \ilProlog (packs) \\
\hline
Bongard-1194 & 0 & 7.8 & 4.74 & 3.93 \\
Bongard-2986 & 0 & 17.8 & 12.7 & 9.8 \\
Bongard-6013 & 0 & 35 & 25 & 18 \\
\hline
Bongard-1007 & 0 & 0.77 & 0.74 & 0.49\\
Bongard-2473 & 0 & 2.07 & 1.82 & 1.13\\
Bongard-4981 & 0 & 4.1 & 3.7 & 2.2\\
\hline
Bongard-1007 & 2 & 7.1 & 7.5 & 2.2\\
Bongard-2473 & 2 & 17.7 & 17.2 & 4.4 \\
Bongard-4981 & 2 & 38 & 35 & 8.2\\
\hline
\end{tabular}
\end{center}
\caption{\ilProlog\ compared to other engines (times in seconds) for 
several data sets and lookahead settings.}
\label{engines:tab}
\end{table}


\subsection{Summary of Experimental Results}

Our experiments confirm that (a) query pack execution in itself is much
more efficient than executing many highly similar queries separately;
(b) existing ILP systems (we use \Tilde\ and \Warmr\ as examples) can use 
this mechanism to their advantage, achieving significant speedups; and c) although a new Prolog engine is needed to achieve this, the current state of
development of this engine is such that with respect to execution speed
it can compete with state-of-the-art engines.  Further, the experiments 
are consistent with our complexity analysis of the execution time of packs.


\section{Related Work}

The re-implementation of \Tilde\ is related to the work by
\shortciteA{Mehta96:proc} who were the first to describe the ``examples in
outer loop'' strategy for decision tree induction.  The query pack
execution mechanism, here described from the Prolog execution point of
view, can also be seen as a first-order counterpart of {\sc Apriori}'s
mechanism for counting item-sets \shortcite{Agrawal96:coll}.

Other lines of work on efficiency improvements for ILP involves
stochastic methods which trade a certain amount of optimality for
efficiency by, e.g., evaluating clauses on a sample of the data set
instead of the full data set \cite{Srinivasan99:jrnl}, exploring the
clause search space in a random fashion \cite{Srinivasan00-prob:other},
or stochastically testing whether a query succeeds on an example
\cite{Sebag97-IJCAI:proc}.  The first of these is entirely orthogonal
to query pack execution and can easily be combined with it.

The idea of optimising sets of queries instead of individual queries
has existed for a while in the database community.  The typical
context considered in earlier research on multi-query optimisation
\shortcite<e.g.,>{Sellis88:jrnl} was that of a database system
that needs to handle disjunctions of conjunctive queries, or of a
server that may receive many queries from different clients in a brief
time interval.  If several of these queries are expected to compute
the same intermediary relations, it may be more efficient to
materialise these relations instead of having them recomputed for each
query.  Data mining provides in a sense a new context for multi-query
optimisation, in which the multi-query optimisation approach is at the
same time easier (the similarities among the queries are more
systematic, so one need not look for them) and more promising (given
the huge number of queries that may be generated at once).

\shortciteA{Tsur98-SIGMOD:proc} describe an algorithm for efficient
execution of so-called query {\em flocks} in this context.  Like our
query pack execution mechanism, the query flock execution mechanism is
inspired to some extent by {\sc Apriori} and is set in a deductive
database setting.  The main difference between our query packs and the
query flocks described by \shortciteA{Tsur98-SIGMOD:proc} is that
query packs are more hierarchically structured and the queries in a
pack are structurally less similar than the queries in a flock.  (A
flock is represented by a single query with placeholders for
constants, and is equal to the set of all queries that can be obtained
by instantiating the placeholders to constants.  Flocks could not be
used for the applications we consider here.)

% dit nog controleren!  (eens kijken of al aanvaard en zo)
\shortciteA{Dekeyser01:other} describe work on multi-query
optimisation in the context of relational databases.  They also
consider tree-like structures in which multiple queries are combined;
the main difference is that their trees are rooted in one single table
from which the queries select tuples, whereas our queries correspond
to joins of multiple tables.  Further, Dekeyser and Paredaens define a
cost measure for trees as well as operators that map trees onto
semantically equivalent (but less costly) trees, whereas we have
considered only the creation of packs and an efficient top-down
execution mechanism for them.  Combining both approaches seems an
interesting topic for further research.

Finally, other optimisation techniques for ILP have been proposed that
exploit results from program analysis
\shortcite{SantosCosta00:proc,Blockeel00-WIP:proc} or from propositional 
data mining technology \shortcite{Blockeel99:jrnl}.  These are complementary
to our pack execution optimisation.  Especially the approach of
\shortciteA{Blockeel99:jrnl} can easily be combined with our pack mechanism.
The techniques discussed by \shortciteA{SantosCosta00:proc} and
\shortciteA{Blockeel00-WIP:proc} involve optimisations for single query 
execution, some of which can to some extent be upgraded to the pack setting.
This is future work.

\section{Conclusions}

There is a lot of redundancy in the computations performed by most ILP
systems.  In this paper we have identified a source of redundancy and
proposed a method for avoiding it: execution of query packs.  We
have discussed how query pack execution can be incorporated in ILP
systems.  The query pack execution mechanism has been
implemented in a new Prolog system called \ilProlog\ and dedicated to data
mining tasks, and two ILP systems have been re-implemented to make use
of the mechanism.  We have experimentally evaluated these
re-implementations, and the results of these experiments confirm that
large speedups may be obtained in this way.  We conjecture that
the query pack execution mechanism can be incorporated in other ILP
systems and that similar speedups can be expected.

The problem setting in which query pack execution was introduced is
very general, and allows the technique to be used for any kind of task
where many queries are to be executed on the same data, as long as the
queries can be organised in a hierarchy.

Future work includes further improvements to the \ilProlog\ engine and
the implementation of techniques that will increase the suitability of
the engine to handle large data sets.  
In the best case one might hope to combine techniques known from
database optimisation and program analysis with our pack execution
mechanism to further improve the speed of ILP systems.


\subsection*{Acknowledgements}

Hendrik Blockeel is a post-doctoral fellow of the Fund for Scientific
Research (FWO) of Flanders.  Jan Ramon is funded by the Flemish
Institute for the Promotion of Scientific Research in Industry (IWT).
Henk Vandecasteele was funded in part by the FWO project G.0246.99,
``Query languages for database mining''.  The authors thank
Luc De Raedt for his influence on this work, Ashwin Srinivasan for
suggesting the term ``query packs'', the anonymous reviewers for their
useful comments, and Kurt Driessens for proofreading this text.  This work
was motivated in part by the Esprit project 28623, Aladin.

\appendix
\section{Preparing the Query for the Meta-interpreter}

%\section*{Appendix}
%\subsection*{Preparing the Query for the Meta-interpreter}

Note that the following preprocessor assumes that the pack of the
form 
{\tt a, (b, (c or d or e) or f or g, (h or i or j))} 
was already transformed to the form 
{\tt a , or([(b, or([c,d,e])), f, (g, or([h,i,j]))])}.

\begin{small}
\tt
\begin{tabbing}
indent \= \kill
prepro\=cess(or(Querys),\= or(NQuerys, PrevNode, NodeNr0, BranchNr, Length),  \kill
      preprocess((A,B),(A,NewB),PrevNode,NodeNr0,LeafNr0,BranchNr,NodeNr1,LeafNr1):- !,\+\\
              preprocess(B,NewB,PrevNode,NodeNr0,LeafNr0,BranchNr,NodeNr1,LeafNr1).\-\\
      
      preprocess(or(Querys),or(NQuerys,PrevNode,NodeNr0,BranchNr,Length),\+\\
                           \>         PrevNode,NodeNr0,LeafNr0,BranchNr,
                                              NodeNr1,LeafNr1):- !,\\
              NodeNr2 is NodeNr0 + 1,\\
              preprocessbranches(Querys,NQuerys,NodeNr0,NodeNr2,LeafNr0,\+\\
                                                 1,NodeNr1,LeafNr1,Length).\-\-\\
      preprocess(A,(A,leaf(PrevNode,BranchNr,LeafNr0)),\+\+\\
                                        PrevNode,NodeNr0,LeafNr0,
                                   BranchNr,NodeNr0,LeafNr1):-\-\\
              LeafNr1 is LeafNr0 + 1.\-\\
\ \\
      
      preprocessbranches([],[],\_,NodeNr,LeafNr,BranchNr, 
                                     NodeNr,LeafNr,BranchNr).\\
      preprocessbranches([Query$|$Querys],[NewQuery$|$NewQuerys],PrevNode,\+ \\
                          \>        NodeNr0,LeafNr0,BranchNr,
                                           NodeNr1,LeafNr1,Length):-\\
              preprocess(Query,NewQuery, \+ \\
                          PrevNode,NodeNr0,LeafNr0,BranchNr,
                                                    NodeNr2,LeafNr2),\-\\
              BranchNr1 is BranchNr + 1,\\
              preprocessbranches(Querys,NewQuerys, 
                                      PrevNode, \+ \\
                                               NodeNr2,LeafNr2,BranchNr1,
                                               NodeNr1,LeafNr1,Length).\-\-\\
\end{tabbing}
\end{small}

%\bibliographystyle{theapa}
%\bibliography{/home/ml/tex/BIB/.mlbib}

\begin{thebibliography}{}

\bibitem[\protect\BCAY{Agrawal, Mannila, Srikant, Toivonen,\ \BBA\
  Verkamo}{Agrawal et~al.}{1996}]{Agrawal96:coll}
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., \BBA\ Verkamo, A.
  \BBOP1996\BBCP.
\newblock \BBOQ Fast discovery of association rules\BBCQ\
\newblock In Fayyad, U., Piatetsky-Shapiro, G., Smyth, P., \BBA\ Uthurusamy,
  R.\BEDS, {\Bem Advances in Knowledge Discovery and Data Mining}, \BPGS\
  307--328. The MIT Press.

\bibitem[\protect\BCAY{A{\"\i}t-Kaci}{A{\"\i}t-Kaci}{1991}]{Ait-Kaci91:other}
A{\"\i}t-Kaci, H. \BBOP1991\BBCP.
\newblock {\Bem Warren's Abstract Machine: A Tutorial Reconstruction}.
\newblock The MIT Press, Cambridge, Massachusetts.
\newblock \\{\tt http://www.isg.sfu.ca/\verb|~|hak/documents/wam.html}.

\bibitem[\protect\BCAY{Blockeel}{Blockeel}{1998}]{Blockeel98:other}
Blockeel, H. \BBOP1998\BBCP.
\newblock {\Bem Top-down induction of first order logical decision trees}.
\newblock Ph.D.\ thesis, Department of Computer Science, Katholieke
  Universiteit Leuven.
\newblock \\{\tt http://www.cs.kuleuven.ac.be/\~{}ml/PS/blockeel98:phd.ps.gz}.

\bibitem[\protect\BCAY{Blockeel\ \BBA\ De~Raedt}{Blockeel\ \BBA\
  De~Raedt}{1997}]{Blockeel97:proc}
Blockeel, H.\BBACOMMA\  \BBA\ De~Raedt, L. \BBOP1997\BBCP.
\newblock \BBOQ Lookahead and discretization in {ILP}\BBCQ\
\newblock In {\Bem Proceedings of the Seventh International Workshop on
  Inductive Logic Programming}, \lowercase{\BVOL}\ 1297 of {\Bem Lecture Notes
  in Artificial Intelligence}, \BPGS\ 77--85. Springer-Verlag.

\bibitem[\protect\BCAY{Blockeel\ \BBA\ De~Raedt}{Blockeel\ \BBA\
  De~Raedt}{1998}]{Blockeel98b:jrnl}
Blockeel, H.\BBACOMMA\  \BBA\ De~Raedt, L. \BBOP1998\BBCP.
\newblock \BBOQ Top-down induction of first order logical decision trees\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 101\/}(1-2), 285--297.

\bibitem[\protect\BCAY{Blockeel, De~Raedt, Jacobs,\ \BBA\ Demoen}{Blockeel
  et~al.}{1999}]{Blockeel99:jrnl}
Blockeel, H., De~Raedt, L., Jacobs, N., \BBA\ Demoen, B. \BBOP1999\BBCP.
\newblock \BBOQ Scaling up inductive logic programming by learning from
  interpretations\BBCQ\
\newblock {\Bem Data Mining and Knowledge Discovery}, {\Bem 3\/}(1), 59--93.

\bibitem[\protect\BCAY{Blockeel, De~Raedt,\ \BBA\ Ramon}{Blockeel
  et~al.}{1998}]{Blockeel98:proc}
Blockeel, H., De~Raedt, L., \BBA\ Ramon, J. \BBOP1998\BBCP.
\newblock \BBOQ Top-down induction of clustering trees\BBCQ\
\newblock In {\Bem Proceedings of the 15th International Conference on Machine
  Learning}, \BPGS\ 55--63.
\newblock {\tt http:}\-{\tt //www.}\-{\tt cs.}\-{\tt kuleuven.}\-{\tt
  ac.}\-{\tt be/\~{}ml/}\-{\tt PS/}\-{\tt ML98-56.ps}.

\bibitem[\protect\BCAY{Blockeel, Demoen, Janssens, Vandecasteele,\ \BBA\
  Van~Laer}{Blockeel et~al.}{2000}]{Blockeel00-WIP:proc}
Blockeel, H., Demoen, B., Janssens, G., Vandecasteele, H., \BBA\ Van~Laer, W.
  \BBOP2000\BBCP.
\newblock \BBOQ Two advanced transformations for improving the efficiency of an
  {ILP} system\BBCQ\
\newblock In {\Bem 10th International Conference on Inductive Logic
  Programming, Work-in-Progress Reports}, \BPGS\ 43--59, London, UK.

\bibitem[\protect\BCAY{Bongard}{Bongard}{1970}]{Bongard70:book}
Bongard, M. \BBOP1970\BBCP.
\newblock {\Bem Pattern Recognition}.
\newblock Spartan Books.

\bibitem[\protect\BCAY{Bratko}{Bratko}{1990}]{Bratko90:other}
Bratko, I. \BBOP1990\BBCP.
\newblock {\Bem Prolog Programming for Artificial Intelligence}.
\newblock Addison-Wesley, Wokingham, England.
\newblock 2nd Edition.

\bibitem[\protect\BCAY{Breiman, Friedman, Olshen,\ \BBA\ Stone}{Breiman
  et~al.}{1984}]{Breiman84:other}
Breiman, L., Friedman, J., Olshen, R., \BBA\ Stone, C. \BBOP1984\BBCP.
\newblock {\Bem Classification and Regression Trees}.
\newblock Wadsworth, Belmont.

\bibitem[\protect\BCAY{Chen\ \BBA\ Warren}{Chen\ \BBA\
  Warren}{1996}]{Chen96:jrnl}
Chen, W.\BBACOMMA\  \BBA\ Warren, D.~S. \BBOP1996\BBCP.
\newblock \BBOQ Tabled evaluation with delaying for general logic
  programs\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 43\/}(1), 20--74.
\newblock {{\tt http://www.cs.sunysb.edu/\~{}sbprolog}}.

\bibitem[\protect\BCAY{Clark\ \BBA\ Niblett}{Clark\ \BBA\
  Niblett}{1989}]{Clark89:jrnl}
Clark, P.\BBACOMMA\  \BBA\ Niblett, T. \BBOP1989\BBCP.
\newblock \BBOQ The {CN2} algorithm\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 3\/}(4), 261--284.

\bibitem[\protect\BCAY{De~Raedt}{De~Raedt}{1997}]{Deraedt97-AI:jrnl}
De~Raedt, L. \BBOP1997\BBCP.
\newblock \BBOQ Logical settings for concept learning\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 95}, 187--201.

\bibitem[\protect\BCAY{De~Raedt\ \BBA\ Dehaspe}{De~Raedt\ \BBA\
  Dehaspe}{1997}]{DeRaedt97-ML:jrnl}
De~Raedt, L.\BBACOMMA\  \BBA\ Dehaspe, L. \BBOP1997\BBCP.
\newblock \BBOQ Clausal discovery\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 26}, 99--146.

\bibitem[\protect\BCAY{De~Raedt\ \BBA\ D\v{z}eroski}{De~Raedt\ \BBA\
  D\v{z}eroski}{1994}]{DeRaedt94-AI:jrnl}
De~Raedt, L.\BBACOMMA\  \BBA\ D\v{z}eroski, S. \BBOP1994\BBCP.
\newblock \BBOQ First order $jk$-clausal theories are {PAC}-learnable\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 70}, 375--392.

\bibitem[\protect\BCAY{De~Raedt\ \BBA\ Van~Laer}{De~Raedt\ \BBA\
  Van~Laer}{1995}]{DeRaedt95-ALT:proc}
De~Raedt, L.\BBACOMMA\  \BBA\ Van~Laer, W. \BBOP1995\BBCP.
\newblock \BBOQ Inductive constraint logic\BBCQ\
\newblock In Jantke, K.~P., Shinohara, T., \BBA\ Zeugmann, T.\BEDS, {\Bem
  Proceedings of the Sixth International Workshop on Algorithmic Learning
  Theory}, \lowercase{\BVOL}\ 997 of {\Bem Lecture Notes in Artificial
  Intelligence}, \BPGS\ 80--94. Springer-Verlag.

\bibitem[\protect\BCAY{Dehaspe\ \BBA\ Toivonen}{Dehaspe\ \BBA\
  Toivonen}{1999}]{Dehaspe99:jrnl}
Dehaspe, L.\BBACOMMA\  \BBA\ Toivonen, H. \BBOP1999\BBCP.
\newblock \BBOQ Discovery of frequent datalog patterns\BBCQ\
\newblock {\Bem Data Mining and Knowledge Discovery}, {\Bem 3\/}(1), 7--36.

\bibitem[\protect\BCAY{Dekeyser\ \BBA\ Paredaens}{Dekeyser\ \BBA\
  Paredaens}{2001}]{Dekeyser01:other}
Dekeyser, S.\BBACOMMA\  \BBA\ Paredaens, J. \BBOP2001\BBCP.
\newblock \BBOQ Query pack trees for multi query optimization\BBCQ\
\newblock \BTR\ 01-04, University of Antwerp.
\newblock {\tt ftp://wins.uia.ac.be/pub/dekeyser/qpt.ps}.

\bibitem[\protect\BCAY{Demoen, Janssens,\ \BBA\ Vandecasteele}{Demoen
  et~al.}{1999}]{Demoen99:proc}
Demoen, B., Janssens, G., \BBA\ Vandecasteele, H. \BBOP1999\BBCP.
\newblock \BBOQ Executing {q}uery {f}locks for {ILP}\BBCQ\
\newblock In Etalle, S.\BED, {\Bem Proceedings of the Eleventh Benelux Workshop
  on Logic Programming}, \BPGS\ 1--14, Maastricht, The Netherlands.
\newblock 14 pages.

\bibitem[\protect\BCAY{Kramer}{Kramer}{1996}]{Kramer96:proc}
Kramer, S. \BBOP1996\BBCP.
\newblock \BBOQ Structural regression trees\BBCQ\
\newblock In {\Bem Proceedings of the Thirteenth National Conference on
  Artificial Intelligence}, \BPGS\ 812--819, Cambridge/Menlo Park. AAAI
  Press/MIT Press.

\bibitem[\protect\BCAY{Mehta, Agrawal,\ \BBA\ Rissanen}{Mehta
  et~al.}{1996}]{Mehta96:proc}
Mehta, M., Agrawal, R., \BBA\ Rissanen, J. \BBOP1996\BBCP.
\newblock \BBOQ {SLIQ}: A fast scalable classifier for data mining\BBCQ\
\newblock In {\Bem Proceedings of the Fifth International Conference on
  Extending Database Technology}.

\bibitem[\protect\BCAY{Muggleton}{Muggleton}{1995}]{Muggleton95-NGC:jrnl}
Muggleton, S. \BBOP1995\BBCP.
\newblock \BBOQ Inverse entailment and {Progol}\BBCQ\
\newblock {\Bem New Generation Computing, Special issue on Inductive Logic
  Programming}, {\Bem 13\/}(3-4), 245--286.

\bibitem[\protect\BCAY{Muggleton\ \BBA\ De~Raedt}{Muggleton\ \BBA\
  De~Raedt}{1994}]{Muggleton94-JLP:jrnl}
Muggleton, S.\BBACOMMA\  \BBA\ De~Raedt, L. \BBOP1994\BBCP.
\newblock \BBOQ Inductive logic programming : Theory and methods\BBCQ\
\newblock {\Bem Journal of Logic Programming}, {\Bem 19,20}, 629--679.

\bibitem[\protect\BCAY{Quinlan}{Quinlan}{1993a}]{Quinlan93:other}
Quinlan, J.~R. \BBOP1993a\BBCP.
\newblock {\Bem C4.5: Programs for Machine Learning}.
\newblock Morgan Kaufmann series in machine learning. Morgan Kaufmann.

\bibitem[\protect\BCAY{Quinlan}{Quinlan}{1993b}]{Quinlan93:proc}
Quinlan, J. \BBOP1993b\BBCP.
\newblock \BBOQ {FOIL}: A midterm report\BBCQ\
\newblock In Brazdil, P.\BED, {\Bem Proceedings of the 6th European Conference
  on Machine Learning}, Lecture Notes in Artificial Intelligence.
  Springer-Verlag.

\bibitem[\protect\BCAY{Santos~Costa, Srinivasan,\ \BBA\ Camacho}{Santos~Costa
  et~al.}{2000}]{SantosCosta00:proc}
Santos~Costa, V., Srinivasan, A., \BBA\ Camacho, R. \BBOP2000\BBCP.
\newblock \BBOQ A note on two simple transformations for improving the
  efficiency of an {ILP} system\BBCQ\
\newblock In {\Bem Proceedings of the Tenth International Conference on
  Inductive Logic Programming}, \lowercase{\BVOL}\ 1866 of {\Bem Lecture Notes
  in Artificial Intelligence}, \BPGS\ 225--242. Springer-Verlag.

\bibitem[\protect\BCAY{Sebag\ \BBA\ Rouveirol}{Sebag\ \BBA\
  Rouveirol}{1997}]{Sebag97-IJCAI:proc}
Sebag, M.\BBACOMMA\  \BBA\ Rouveirol, C. \BBOP1997\BBCP.
\newblock \BBOQ {T}ractable {I}nduction and {C}lassification in {F}irst-{O}rder
  {L}ogic via {S}tochastic {M}atching\BBCQ\
\newblock In {\Bem Proceedings of the 15th International Joint Conference on
  Artificial Intelligence}. Morgan Kaufmann.

\bibitem[\protect\BCAY{Sellis}{Sellis}{1988}]{Sellis88:jrnl}
Sellis, T. \BBOP1988\BBCP.
\newblock \BBOQ Multiple-query optimization\BBCQ\
\newblock {\Bem ACM Transactions on Database Systems}, {\Bem 13\/}(1), 23--52.

\bibitem[\protect\BCAY{Srinivasan}{Srinivasan}{1999}]{Srinivasan99:jrnl}
Srinivasan, A. \BBOP1999\BBCP.
\newblock \BBOQ A study of two sampling methods for analysing large datasets
  with {ILP}\BBCQ\
\newblock {\Bem Data Mining and Knowledge Discovery}, {\Bem 3\/}(1), 95--123.

\bibitem[\protect\BCAY{Srinivasan}{Srinivasan}{2000}]{Srinivasan00-prob:other}
Srinivasan, A. \BBOP2000\BBCP.
\newblock \BBOQ A study of two probabilistic methods for searching large spaces
  with {ILP}\BBCQ\
\newblock \BTR\ PRG-TR-16-00, Oxford University Computing Laboratory.

\bibitem[\protect\BCAY{Srinivasan, Muggleton,\ \BBA\ King}{Srinivasan
  et~al.}{1995}]{Srinivasan95:proc}
Srinivasan, A., Muggleton, S., \BBA\ King, R. \BBOP1995\BBCP.
\newblock \BBOQ Comparing the use of background knowledge by inductive logic
  programming systems\BBCQ\
\newblock In De~Raedt, L.\BED, {\Bem Proceedings of the Fifth International
  Workshop on Inductive Logic Programming}.

\bibitem[\protect\BCAY{Tsur, Ullman, Abiteboul, Clifton, Motwani, Nestorov,\
  \BBA\ Rosenthal}{Tsur et~al.}{1998}]{Tsur98-SIGMOD:proc}
Tsur, D., Ullman, J., Abiteboul, S., Clifton, C., Motwani, R., Nestorov, S.,
  \BBA\ Rosenthal, A. \BBOP1998\BBCP.
\newblock \BBOQ Query flocks: {A} generalization of association-rule
  mining\BBCQ\
\newblock In {\Bem Proceedings of the {ACM} {SIGMOD} International Conference
  on Management of Data ({SIGMOD}-98)}, \lowercase{\BVOL}\ 27,2 of {\Bem ACM
  SIGMOD Record}, \BPGS\ 1--12, New York. ACM Press.

\end{thebibliography}


\end{document}

