2. 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.

3. Packed execution of packs: a compiled query pack is executed where queries share as much as possible.
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 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 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 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 1 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.

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 ′ +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 H queries. Remember that