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 [23]. 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.