TREE: the Heuristic Driven Join Strategy of a RETE-Like Matcher

TL;DR

This paper introduces TREE, a novel heuristic-driven join strategy for production system matchers, designed to significantly reduce the computational cost of matching rules against working memory. By leveraging constraint propagation and heuristic relaxation based on symbol sharing rather than traditional condition element matching, TREE achieves substantial performance gains, reducing comparison counts by up to two orders of magnitude compared to the standard RETE algorithm.

What Problem Does This Paper Address?

Production systems, like SOAR, rely on a "match" process to determine which rules should fire based on the current state of the "working memory" (WM). This matching process, particularly the "join" step where conditions of a rule are combined, can become computationally prohibitive, especially when the data formalism is restricted (e.g., to triples) and rules have many conditions. This leads to a combinatorial explosion in the search space. Existing solutions like condition ordering, restricted expressiveness, and hashing techniques have limitations. Hashing, for instance, can introduce overhead and doesn't always guarantee significant improvements. The paper aims to address this by developing a more efficient join strategy that avoids hashing and focuses on reducing the join search space through intelligent indexing.

Methods

The core of TREE's innovation lies in its heuristic-driven join strategy. Unlike the standard RETE algorithm, which uses condition elements (CEs) to define indexes for matching, TREE uses a scheme based on the sharing of references to symbols within WMEs.

Key methodological aspects include:

  • Symbol-based Indexing: Instead of indexing based on which CE a WME matches, TREE indexes WMEs based on the symbols they contain and their positions (e.g., a WME [FRV] is indexed by [F??], [?R?], and [??V]). This indexing is established at compile time and is independent of the rule base.
  • Constraint Propagation (P): This function takes an existing partial instantiation (IME) and a CE, and applies the bound variables from the IME to the CE. This narrows down the potential matches.
  • Heuristic Constraint Relaxation (R): When the result of constraint propagation (CP) is not a direct index, TREE uses a heuristic function R to find a "subsuming relaxed pattern" that is an index. This relaxation is based on expected cardinalities of different pattern types, aiming to find an index that is larger than the true solution space but still efficient to search.
  • Modified RETE Procedures: The paper presents modified ADD-IME and ADD-WME procedures that incorporate TREE's indexing and join strategy, replacing RETE's direct CE-based indexing with the R(i, P(i, CE)) index.

Datasets

The paper does not introduce new datasets. Instead, it uses five real-world rule-based programs developed in their laboratory as benchmarks:

  • MAB: The "monkey and bananas" problem.
  • ALEXIA: A qualitative model for hypertension.
  • CHART: A syntactic chart parser.
  • AMD: A semantic analyzer for natural language.
  • ABACAB: A blackboard controller.

These programs are described as satisfying the assumption of a relational paradigm, which is crucial for TREE's heuristic assumptions.

Key Insights and Ideas

  • Symbol Sharing is a Powerful Indexing Primitive: The paper demonstrates that indexing based on symbol sharing, rather than just CE membership, can be a highly effective way to organize working memory and intermediate join results.
  • Heuristics for Index Selection are Crucial: When direct indexing isn't possible, a well-chosen heuristic relaxation function (R) can still guide the system to efficient search spaces, even if they are slightly larger than the ideal solution space.
  • Compile-Time Optimization Pays Off: TREE's ability to determine join strategies and indexes at compile time, independent of the rule base, offers advantages in terms of dynamic rule compilation and reduced runtime overhead compared to some other approaches.
  • Contextual Constraints Trump Definitional Ones: The results suggest that for many real-world problems with relational data, the constraints derived from variable bindings in partial instantiations are more powerful for focusing searches than the explicit definitions of the condition elements themselves.

Key Results

The experimental results are compelling:

  • Significant Reduction in Comparisons: TREE consistently outperformed the standard RETE algorithm in terms of the number of comparisons per join attempt. This reduction ranged from a factor of 1 up to nearly two orders of magnitude (e.g., for W-joins of ABACAB, RETE/TREE ratio was 74.4).
  • Lower Join Attempt Counts: For most programs, TREE performed a similar or even lower number of non-empty join attempts compared to RETE, indicating more efficient pruning of the search space.
  • Overall Performance Improvement: The combined effect of reduced comparisons and join attempts led to a substantial overall performance improvement, with total comparison counts being much smaller with TREE.
  • Heuristic Validity: The experimental data supported the heuristic assumptions about pattern cardinalities, showing that [?R?] patterns were indeed the most frequent and that constraint relaxation effectively mapped to smaller, more manageable index patterns like [F??] and [??V].

Limitations and Future Work

  • Heuristic Dependence: The performance of TREE is inherently dependent on the quality of its heuristic constraint relaxation function (R) and the predefined indexing scheme. The paper acknowledges that efficiency depends on R, which in turn depends on the specific data formalism and problem domain.
  • WME Removal Not Deeply Explored: While the paper mentions that WME removal is handled similarly to additions, the evaluation of this aspect is not deeply explored.
  • Comparison with Hashing: While H-RETE is mentioned as a comparable approach, TREE was not directly tested against it on the same benchmarks.
  • Future Work Suggestions:
    • Exploring other constraint relaxation strategies.
  • Investigating combinations of TREE's and RETE's indexing schemes.
  • Applying TREE to other systems like SOAR, which shares similar characteristics.
  • Further exploring the impact of WM size on performance.

Summary updated

BibTeX
@inproceedings{1993tree,
  title = {{TREE: the Heuristic Driven Join Strategy of a RETE-Like Matcher}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure