Abstract
In AI production systems, the "match" phase—identifying which rules apply to current data—is frequently the primary performance bottleneck. This is particularly acute in systems like SOAR that utilize triple-based data formalisms. This paper introduces TREE, an optimized pattern-matching algorithm that replaces standard condition-based indexing with a heuristic-driven "constraint relaxation" strategy. By indexing data based on shared symbols rather than rule conditions, TREE reduces join-step comparisons by up to two orders of magnitude compared to the classic RETE algorithm.
Introduction
Traditional production systems often struggle with the "combinatorial explosion" during the join step, where multiple conditions must be cross-referenced to satisfy a rule. In triple-based systems (e.g., [Object Attribute Value]), a single condition may match nearly every item in memory, leading to massive, inefficient search spaces. While the classic RETE algorithm optimizes this by saving state, its indexing scheme remains tied to specific condition elements (CEs). TREE addresses this by shifting the focus from rule definitions to the contextual constraints provided by bound variables.
The TREE Algorithm
TREE is a state-saving matcher that deviates from RETE through several key innovations:
- Symbol-Based Indexing: Unlike RETE's condition-centric approach, TREE indexes data based on shared references to symbols (identifiers, attributes, or values). This recognizes that in triple-based systems, the most discriminant information is often a unique object ID rather than the rule structure itself.
- Constraint Propagation and Relaxation: During rule processing, TREE utilizes variables already bound to values as "contextual constraints." If a propagated constraint does not perfectly match a pre-defined index, TREE employs a heuristic to "relax" the constraint to the most efficient available index.
As shown in the lattice above, a requirement for a fully specified triple [FRV] can be relaxed to search broader indexes like [F?V] or [?RV] if the specific index is unavailable. This strategy is built on the "relational paradigm," assuming that indexing by "Object" or "Value" is generally more efficient than indexing by "Relation."
Experimental Evaluation
The algorithm was evaluated using five rule-based programs representing diverse AI tasks, ranging from planning to natural language processing.
The testbeds included:
- MAB: A classic AI planning task (Monkey and Bananas).
- ALEXIA: A qualitative model for hypertension.
- CHART: A syntactic chart parser.
- AMD: A semantic analyzer for natural language.
- ABACAB: A blackboard controller.
Key Results
TREE demonstrated significant performance improvements over standard RETE implementations:
- Comparison Reduction: For complex programs like ABACAB and AMD, TREE reduced the total number of comparisons by factors ranging from 10 to 74.
- Efficiency Gains: The average number of comparisons per join was consistently lower. In the ALEXIA program, RETE averaged 111.2 comparisons per I-join, whereas TREE averaged only 6.5.
- Scalability: TREE’s symbol-based indexes remain relatively small as Working Memory (WM) grows, providing a distinct advantage over RETE’s condition-based memories, which tend to explode in size.
Discussion and Conclusion
While TREE offers massive gains for complex systems, it does carry overhead that may not be justified for very simple programs like MAB, where RETE occasionally performed better. Furthermore, its effectiveness is tied to the "relational paradigm"; it may be less effective in systems where condition elements are naturally more discriminant. Future work may explore hybrid approaches that combine TREE’s heuristic indexing with traditional RETE indexing to maximize flexibility across diverse production system domains.
Summary updated