Origin of the Rete Algorithm

To compensate for the “fun break” in my Valentine posting, I decided to tackle a much more technical and deep subject: The Rete Algorithm, and in this post more specifically, the origin of the Rete Algorithm.

As you probably know if you have read any Rules material, Rete is the dominant algorithm out there.  There are actually 2 schools: those that believe in Inference and those who don’t.  Rete is the foundational algorithm for executing rules in Inference mode.  I discussed in an earlier post the difference and importance of the various algorithms used in commercial BRMS.  You certainly do not need to know how it works to use those kinds of technologies — you do not need to understand mechanics to drive a car.  That being said, I know that some curious minds out there do enjoy a little sneak peek under the hood now and then.   In today’s post, I will focus on the origin of the Rete Algorithm.  In part 2, I will explain how it really works.

My First Encounter

Dr Charles L. Forgy developed this infamous algorithm in the late 70’s but it took a little while for the algorithm to become widely popular, when Business Rules technology finally emerged.  I do not recall that Rete was taught at school back then when I got my Masters in Computer Science.  We did a fair amount of Artificial Intelligence though.  When I was a young consultant, I got my hands dirty with Expert Systems before I was introduced to ILOG Rules.  As I joined the company, I became a big fan of the technology and eventually JRules when it was released.  I remember when Changhai Ke in person came to the US to teach us the Rete algorithm and I finally learned the internals of this great technology.  Of course ILOG, Blaze and most inference engine providers have made slight modifications to the algorithm to improve its speed, or sometimes add capabilities.  Unfortunately you will have to wait until my next post to dive deep in the algorithm.

What surprised me the most though through the years is that there is actually little literature on the algorithm itself.  I was shocked when I joined Blaze Software and only a handful (if that many) knew how it actually worked inside.  As I finally accepted, you do not need to know how it works to use it but I thought that, as vendors, we had a duty of knowing “mechanics”.  It was over 10 years ago and I was still young and purist back then.

About Rete

Rete was the product of Charles’s work at Carnegie Mellon University.  While the algorithm has been refined from the original working paper to his PhD thesis, we often reference the final paper published in 1982.  The genius of the approach is to keep in memory the “status” of individual condition evaluations removing the need for constant calculations.  As a result, rules project that are by definition pattern-matching intensive can be evaluated much faster, especially as new facts need to be propagated, than using a systematic approach.

“Inference” projects are the ideal use case for this approach since they make interrelated decisions — rule1 (High Spender) implies rule2 (VIP Customer) which implies rule3 (Free Shipping), etc. — that would be tedious to recompute constantly as we look at facts.  In this example, a new fact of a significant purchase return might affect the initial decision eventually leading to shipping charges to be added to the invoice.  This is a simplistic example since we typically have all facts upfront in a checkout service.  Most academic examples of inference projects are more complicated to describe in business terms as they involve monkeys trying to reach a banana by jumping on tables and chairs, or guests to seat next to each other based on interest.

The best usage of the Rete network I have seen in a business environment was likely Alarm Correlation and Monitoring.  This implies a “stateful” kind of execution where alarms are received over time as they occur.  When you consider that the actual Telecom network is made of thousands of pieces of equipment to keep in “mind” while processing the alarms, there is no wonder that Rete outperforms brute force.  When one alarm is raised on one Router, the Rete network does not have to reprocess all past events to realize that we reached the threshold of 5 major alerts on the same piece of equipment and trigger the proper treatment, eventually providing a probable diagnostic.  Hours of processing time turned into seconds in Network Management Systems.  Fabulous.

All Business Rules projects do not require inference though.  When you have all data known upfront and there is very little back-and-forth between the rules, then sequential maybe as fast or faster than Rete.  When Inference is needed though, per a French saying “y a pas photo” — meaning literally “no need for a picture”, there is no doubt.

Origin of the Name

I heard many different origins for the name of the algorithm.  They all refer to the structure created in memory, the Rete Network, that looks like a complicated mesh of nodes and links.  I wonder if you will guess which one is the real one! I will publish the real answer given to me personally by Charles in the next post!

Technically the answer is not an acronym so the right way to refer to RETE is not in all-caps.  So I should correct it and from now on refer to it as “Rete”.  I have done better over the years but I still like uppercase!

Many Retes

The original Rete algorithm evolved over the years.

Most BRMS vendors developed their own algorithm that are known in the elite circles as XRete or uni-rete, which involved mostly performance improvements and built-in support for collections for example.

Rete 2 is the version that Charles developed in his own engine called OPS/J.  The performance improvements broke the legendary “Rete wall” which referred to the dramatic performance degradation when the number of objects in working memory increased.

Rete 3 is the evolution of Rete 2 developed for RulesPower and subsequently integrated with Blaze Advisor.  I am not at liberty to tell you much about the trade secrets in there.  To avoid any wrath from FICO, I will not say anything.

So what is next?

We announced in our blog last year that Charles had come up with yet another variation on the Rete algorithm that dwarfs the performance of its predecessor.  You might wonder why he did not call it Rete 4, following the established naming scheme…

Was that in celebration of Windows-NT which broke also the number sequence previously established?

I will not make you guess this time!  Rete 4 is the name of a private Italian television channel and was not available for grab without copyright infringement at worst and confusion at best.  For some time, Charles referred to the algorithm as TECH but acknowledged that it was not Google-able so decided to rename it Rete-NT.

I am looking forward to part 2 now…  Talk to you soon!