Origin of the Rete Algorithm

Rete Algorithm Demystified: Part 1a

After my more light-hearted Valentine’s post on which technologies would make a great date for BRMS, I’m going to tackle a much more technical subject: The Rete algorithm. More specifically, I’m going to cover the origin of the Rete algorithm. As you probably know, especially if you’ve read anything about business rules, Rete is the dominant algorithm out there. 2 schools of thought exist in the business rules community: those that believe in inference and those that don’t. Rete is for the believers and the foundational algorithm for executing rules in inference mode. However, not all rules projects require inference. In cases where all data that is needed is known upfront and there are little dependencies between the rules, sequential mode may be as fast or faster than Rete. I discussed in an earlier post the difference and importance of the various algorithms used in commercial BRMS.

My First Encounter

While the algorithm has been around since the 80’s, it was not widely adopted until business rules technology emerged. I do not recall learning Rete when I got my Masters in Computer Science. We did work with a fair amount of Artificial Intelligence. When I was a young consultant, I got my hands dirty with expert systems. Then I was introduced to BRMS ILOG Rules from ILOG and later joined the company. I became a big fan of this technology (and JRules when it was later released). I remember when guru Changhai Ke came to the US to teach us the Rete algorithm. That’s when I finally understood and fully appreciated its brilliance.

While ILOG, Blaze and most inference engine providers have slightly modified the algorithm to improve speed or add capabilities, they would not exist without it. Yet surprisingly, in all my years working with business rules, I’ve come across very little literature on this revolutionary algorithm. When I joined Blaze Software, I was shocked to learn that only a handful or people knew how it actually worked. I realized that in the same way you don’t need to understand the mechanics of a car to drive one, you don’t need to understand the algorithms of a business rules engine to use one. That being said, I know that some curious minds enjoy looking under the hood.

Origin of Rete

Dr Charles L. Forgy developed Rete in the late 70’s at Carnegie Mellon University. He first published his algorithm in his 1982 working paper. While his PhD thesis further refined the algorithm, we often reference his original paper. The genius of his algorithm is that it keeps in memory the “status” of individual condition evaluations. This removes the need for constant calculations. As a result, pattern-matching intensive rules projects can be evaluated much faster than using a systematic approach.

From Academia to Business

“Inference” projects, where rules are interrelated and interdependent, are the ideal use case for Rete. Most academic examples can get really complicated. For example, how to best organize a seating chart based on familiarity and compatibility. Or, what’s the most effective way for a group of monkeys to get to a bunch of bananas. In the business world, the use case doesn’t need to be as complicated to still benefit from using Rete. For example, think about all the rules that are necessary to manage a loyalty rewards program. You have various rules that determine a member’s status, calculates “points,” and applies rewards. The total points of a member impacts their status. And their status impacts both the points calculation and rewards eligibility.

The best business use case I have seen is Alarm Correlation which is used to identify unusual behavior in telecommunication networks. Alarm Correlation requires a “stateful” kind of execution because alarms occur over time and need to be “remembered” in order to find correlations. When you consider that a telco network is made up of thousands of pieces of equipment that need to be kept “in mind” when the alarms are processed, Rete is definitely the way to go. Through Rete, when an alarm is raised on a router, you don’t have to reprocess all past events to determine that this alarm is the 5th one you’ve had this month. Hours of processing time turn into seconds with Rete.

Origin of its Name

Over the years, I’ve heard many different origin stories 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. Do you know which story is real? I’ll share the story personally handed to me by Charles himself in the next post! As a clue and correction on my part, Rete is not an acronym. In my older posts, I’ve used all caps but will use the correct form moving forward. Although, I think it looks cool in uppercase!

The Rete Evolution

As mentioned earlier, the Rete algorithm has evolved over the years (and not just by Charles).

• Most BRMS vendors developed their own algorithm known in elite circles as XRete or uni-rete. These niche versions improve performance and add built-in support for collections and other use cases.
• 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. To avoid any wrath from FICO, I will not divulge any trade secrets and will say no more.

Rete “4.0”

Last year we announced that Charles had released Rete-NT, the latest version of the algorithm that outperforms its predecessors. Why isn’t it called Rete 4? Was it a nod to Windows-NT which also deviated from the number sequence of its predecessors? I won’t make you guess on this one. It turns out, Rete 4 is the name of a private Italian television channel. To avoid potential copyright infringement and confusion, Rete-NT stuck. Fun fact: Charles referred to the algorithm as TECH at one point, but, he acknowledged that it was not Google-able.