Rete algorithm
From Free net encyclopedia
←Older revision | Newer revision→
The Rete algorithm is an efficient pattern matching algorithm for implementing rule-based ("expert") systems. The Rete algorithm was designed by Dr. Charles L. Forgy of Carnegie Mellon University in 1979. Rete has become the basis for many popular expert systems, including JRules, OPS5, CLIPS, JESS, Drools, and LISA.
A naïve implementation of an expert system might check each rule against the known facts in the Knowledge base, firing that rule if necessary, then moving on to the next rule (and looping back to the first rule when finished). For even moderate sized rules and facts knowledge-bases, this naïve approach performs far too slowly.
The Rete algorithm (usually pronounced either 'REET' or 'REE-tee', from the Latin 'rete' for net, or network) provides the basis for a more efficient implementation of an expert system. A Rete-based expert system builds a network of nodes, where each node (except the root) corresponds to a pattern occurring in the left-hand-side of a rule. The path from the root node to a leaf node defines a complete rule left-hand-side. Each node has a memory of facts which satisfy that pattern.
As new facts are asserted or modified, they propagate along the network, causing nodes to be annotated when that fact matches that pattern. When a fact or combination of facts causes all of the patterns for a given rule to be satisfied, a leaf node is reached and the corresponding rule is triggered.
The Rete algorithm is designed to sacrifice memory for increased speed. In most cases, the speed increase over naïve implementations is several orders of magnitude (because Rete performance is theoretically independent of the number of rules in the system). In very large expert systems, however, the original Rete algorithm tends to run into memory consumption problems. Other algorithms, both novel and Rete-based, have since been designed which require less memory.
Contents |
Rete II
In the 1980s Charles L. Forgy developed a successor to the Rete algorithm named Rete II [1]. Unlike the original Rete (which is public domain) this algorithm was not disclosed. Rete II claims better performance for more complex problems (even orders of magnitude).
Rete III
While at RulesPower, now acquired by Fair Isaac, Charles L. Forgy developed Rete III [2], a successor to Rete II. Rete III claims even better performance than Rete II for problems that involve both complex rules and large collections of facts.
Reference
- Charles Forgy, "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, 19, pp 17-37, 1982
External links
- Detailed and accessible description of Rete, also describes variant named Rete/UL, optimised for large systems (PDF)
- Rete information on Drools.org, Drools is an open source rules engine implementation
- Rete information on Jess
- ILOG JRules product page, JRules is a pure Java rule engine offering. JRules uses a proprietary Rete algorighm for one of its optimized engine execution choices.
- ILOG Rules for .NET product page, Rules for .NET is a pure .NET rule engine offering. Rules for .NET uses a proprietary Rete algorighm for one of its optimized engine execution choices.
- Blaze Advisor product page, rules management system that uses Rete III
- According to the Rulesnl:Rete algoritme