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

Abstract

TREE is an optimized RETE-like patternmatching algorithm. It has been designed for a production system whose restricted data formalism leads to a highly combinatorial join step like in SoAR. TREE aims at reducing the join search spaces without using hashing techniques. Its join strategy uses constraint propagation to define the solution space of a join, then a constraint relaxation to determine the index to be used in the join computation. Constraint relaxation is heuristic driven and based on the relational paradigm. Unlike RETE, the indexing scheme TREE requires is not based on the membership of condition elements but on the sharing of references to symbols. On the basis of experimental evidence, TREE's strategy showed better results than the standard RETE one. The number of comparisons during join steps has been reduced by a factor ranging from 1 to nearly two orders of magnitude.