Some algebra then gives

$$\frac{T_{s}}{T_{p}}=\frac{b^{d-l}c_{l}R_{0,l}+R_{l+1,d}}{c_{l}+1}\tag{13}$$

which needs to hold for all l .  We can interpret this as follows:  for a certain level l , c t 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.

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 t increases and monotonically with l . It is clear that if at some point c t becomes much larger than 1, a speedup factor of roughly b = t is obtained. On the other hand, if c t is smaller than 1, then the behaviour of b - t c t is crucial. Now,

$$b^{d-l}c_{l}=\frac{\bar{t}_{l}+\frac{1}{b}\bar{t}_{l-1}+\cdot\cdot\cdot+\frac{1}{b^{l}}\bar{t}_{0}}{\bar{t}_{d}+\frac{1}{b}\bar{t}_{d-1}+\cdot\cdot\cdot+\frac{1}{b^{d-1-1}}\bar{t}_{l+1}}.$$

Our conclusion is similar to that for the one-level pack. If for some l, c t >> 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 i p = t times more often), then a speedup of i p − t can be expected. If c t << 1, which will usually be the case for all except those near d, the speedup can roughly be estimated as ˆ ı / ˆ ı d . The maximum of all these factors will determine the actual speedup.

## 4. 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.

## 4.1 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.

## 4.1.1 Induction Of Decision Trees

The first algorithm we discuss is Tilde (Blockeel & De Raedt, 1998), 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 ss 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