TL;DR
Inductive Logic Programming (ILP) is notoriously slow because it evaluates thousands of highly similar logical queries independently, leading to massive computational redundancy. This paper introduces "query packs"—a method to bundle queries with shared prefixes into a tree structure—alongside a custom Prolog engine (ilProlog) designed to execute them simultaneously. This approach eliminates redundant computations, yielding execution speedups of up to 75x on standard ILP tasks.
What Problem Does This Paper Address?
Inductive Logic Programming (ILP) and relational data mining algorithms learn rules from complex, multi-relational data (first-order logic). To find the best rules, these algorithms use a "generate-and-test" approach: they generate a massive space of candidate hypotheses and test them against a dataset.
The core bottleneck is that these candidate hypotheses are usually evaluated one by one. Because hypotheses are generated by incrementally refining previous ones, they share a lot of structure. For example, an algorithm might test p(X), q(X,a) and then test p(X), q(X,b). A standard Prolog engine will compute the shared prefix p(X) from scratch for every single variation. When scaling to large datasets, this redundant computation makes ILP practically infeasible.
Methods
To eliminate this redundancy, the authors propose a new execution strategy based on Query Packs:
- Tree-Structured Queries: Instead of a flat list of separate queries, similar queries are merged into a prefix tree. The shared parts form the trunk, and the variations form the branches (represented as a nested
ordisjunction). - Smart Pruning: Standard Prolog evaluates disjunctions sequentially and backtracks exhaustively. The authors designed a new execution mechanism where, if a branch of the query pack succeeds for a specific training example, that branch is "pruned" and not re-evaluated for that example during backtracking.
- Low-Level WAM Extension: The authors found that implementing this logic as a high-level Prolog meta-interpreter actually slowed down execution due to overhead. To achieve real speedups, they modified the Warren Abstract Machine (WAM)—the low-level architecture underlying most Prolog engines. They introduced a "pack table" to manage alternatives in memory efficiently, creating a dedicated engine called
ilProlog. - Algorithm Integration: They integrated this pack execution mechanism into two existing ILP systems: TILDE (a first-order decision tree inducer) and WARMR (a frequent pattern discovery algorithm).
Datasets
The authors evaluated their approach on two types of datasets:
- Mutagenesis: A classic, real-world ILP benchmark containing structural descriptions of 230 molecules, used to test both classification and regression tasks.
- Bongard Problems: An artificial dataset generator based on visual pattern recognition tasks (geometric figures). The authors used this to generate datasets of varying sizes (from 1,000 to over 6,000 examples) to test how the query packs scale with data volume and hypothesis complexity.
Key Insights and Ideas
- Redundancy is the real enemy of ILP scaling: The sheer size of the hypothesis space is a known issue, but the similarity of the hypotheses is an under-exploited optimization opportunity.
- "Broom-like" structures yield the best speedups: Theoretical complexity analysis shows that query packs shaped like a broom—a long shared prefix that branches heavily at the very end—provide the most dramatic efficiency gains.
- High-level hacks aren't enough: Attempting to optimize query execution at the software level (via Prolog meta-interpreters) fails because the administrative overhead destroys the efficiency gains. True optimization requires hacking the compiler/abstract machine level.
Key Results
- Massive gains for Decision Trees (TILDE): Using query packs resulted in net speedups ranging from 2x to 75x compared to executing queries separately. The speedup scales super-linearly with the complexity of the target hypothesis; deeper trees create larger packs with more shared prefixes, maximizing the benefit of the WAM extensions.
- Solid gains for Frequent Patterns (WARMR): WARMR also saw significant speedups, typically between 1.5x and 8x. The gains are slightly lower than TILDE because WARMR uses a level-wise Apriori-style search. It prunes infrequent branches early, which naturally narrows the query packs at deeper levels, reducing the amount of shared computation available to optimize.
- Engine Competitiveness: The custom
ilPrologengine, even without packs enabled, performs competitively with highly optimized, state-of-the-art engines like MasterProLog and SICStus, proving the speedups are genuine and not the result of a weak baseline.
Limitations and Future Work
- Limitations: Query packs require more memory to store the complex tree structures and the associated pack tables during execution. Additionally, in specific edge cases (like very deep WARMR searches where most branches have already been pruned), the administrative overhead of managing the pack can occasionally outweigh the computational savings.
- Future Work: The authors suggest that optimizing groups of queries is a mature field in relational databases (multi-query optimization) and that techniques from that domain could be adapted for ILP. They also propose combining query packs with stochastic search methods (evaluating clauses on random samples of data) to push efficiency even further.
Summary updated