is formed by adding one or more literals to the query); evaluate these refinements on the relevant subset of the data, 2 computing, e.g., the information gain (Quinlan, 1993a) 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 (Blockeel & De Raedt, 1997), 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. Example 4 Assume the node currently being refined has the following query associated with it: ?- 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 triangle(A,F)
circle(A,H)
small(A,I)

$${\mathrm{circle(A,C),leftof(A,C,D),above(A,D,E)}}$$

large(A,J)

in(A,E,K)
in(A,D,L)
in(A,C,M)
above(A,E,N)
above(A,D,O)
above(A,C,P)
leftof(A,E,Q)
leftof(A,D,R)
leftof(A,C,S)
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 circle(A,C), leftof(A,C,D), above(A,D,E); when executing a pack this search is done only once.

## 4.1.2 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 (Muggleton, 1995). 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,