TREAT or RETE, neither, LEAPS is best.

Chances are you have arrived at this page because you are contemplating building a rule evaluation system. Here is my nutshell advice.


The algorithmic complexity (big O) of TREAT and RETE are identical. Except for active-database implementations the TREAT vs. RETE debate is a game of small constants. By small, algorithmically I mean something on like 2 to 4 and otherwise small enough that other implementation issues can easily overcome the algorithmic superiority of TREAT. Although I pioneered these results, they have been duplicated by many others. In my opinion the best work has been done by Wang and Hanson who developed detailed cost models concerning the precise differences between TREAT and RETE.

As a responsible scientist I have to admit the a RETE implementation is easier than a TREAT implementation. In particular Forgy clearly outlines a single pass method for producing code for an abstract RETE machine. Although Bernie Lofaso and I did develop an abstract target for TREAT, I stopped working on this before we were able to refine that target to the extent that code could be produced in a single pass. If you are looking for a place to make a contribution, the definition of a TREAT abstract machine and single pass rule compilation algorithms would be a fine contribution.

LEAPS - asymptotically better:

In the debate concerning the use of the RETE or TREAT it commonly lost that David Brant and I developed a lazy evaluation scheme, (LEAPS), for the evaluation of rule-based systems. This algorithm collapses the space complexity of this problem to linear. In a scaling study we demonstrated polynomial improvements in time and space. Tom Hetherington has done some further extensions to the algorithm which result in asymptotic improvement in time-complexity as well.