imported>ShimmeringStones: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-12-30T12:44:32Z

growthexperiments-addlink-summary-summary:2|0|0

← Previous revision		Revision as of 12:44, 30 December 2025
Line 35:		Line 35:
	The "right" (''beta'') side of the graph chiefly performs joins between different WMEs. It is optional, and is only included if required. It consists of 2-input nodes where each node has a "left" and a "right" input. Each beta node sends its output to a ''beta memory''.		The "right" (''beta'') side of the graph chiefly performs joins between different WMEs. It is optional, and is only included if required. It consists of 2-input nodes where each node has a "left" and a "right" input. Each beta node sends its output to a ''beta memory''.

	In descriptions of Rete, it is common to refer to token passing within the beta network. In this article, however, we will describe data propagation in terms of WME lists, rather than tokens, in recognition of different implementation options and the underlying purpose and use of tokens. As any one WME list passes through the beta network, new WMEs may be added to it, and the list may be stored in beta memories. A WME list in a beta memory represents a partial match for the conditions in a given production.		In descriptions of Rete, it is common to refer to [[token passing]] within the beta network. In this article, however, we will describe data propagation in terms of WME lists, rather than tokens, in recognition of different implementation options and the underlying purpose and use of tokens. As any one WME list passes through the beta network, new WMEs may be added to it, and the list may be stored in beta memories. A WME list in a beta memory represents a partial match for the conditions in a given production.

	WME lists that reach the end of a branch of beta nodes represent a complete match for a single production, and are passed to terminal nodes. These nodes are sometimes called ''p-nodes'', where "p" stands for ''production''. Each terminal node represents a single production, and each WME list that arrives at a terminal node represents a complete set of matching WMEs for the conditions in that production. For each WME list it receives, a production node will "activate" a new production instance on the "agenda". Agendas are typically implemented as [[Priority queue\|prioritised queues]].		WME lists that reach the end of a branch of beta nodes represent a complete match for a single production, and are passed to terminal nodes. These nodes are sometimes called ''p-nodes'', where "p" stands for ''production''. Each terminal node represents a single production, and each WME list that arrives at a terminal node represents a complete set of matching WMEs for the conditions in that production. For each WME list it receives, a production node will "activate" a new production instance on the "agenda". Agendas are typically implemented as [[Priority queue\|prioritised queues]].
Line 139:		Line 139:

	===Rete-III===		===Rete-III===
	In the early 2000s, the Rete III engine was developed by Charles Forgy in cooperation with FICO engineers. The Rete III algorithm, which is not Rete-NT, is the FICO trademark for Rete II and is implemented as part of the FICO Advisor engine. It is basically the Rete II engine with an API that allows access to the Advisor engine because the Advisor engine can access other FICO products.<ref>{{Cite web \|url=http://dmblog.fico.com/2005/09/what_is_rete_ii.html \|title=What is Rete III? - Decision Management Blog \|access-date=2014-08-05 \|archive-date=2014-08-08 \|archive-url=https://web.archive.org/web/20140808061650/http://dmblog.fico.com/2005/09/what_is_rete_ii.html \|url-status=dead }}</ref>		In the early 2000s, the Rete III engine was developed by Charles Forgy in cooperation with FICO engineers. The Rete III algorithm, which is not Rete-NT, is the FICO trademark for Rete II and is implemented as part of the FICO Advisor engine. It is basically the Rete II engine with an [[API]] that allows access to the Advisor engine because the Advisor engine can access other FICO products.<ref>{{Cite web \|url=http://dmblog.fico.com/2005/09/what_is_rete_ii.html \|title=What is Rete III? - Decision Management Blog \|access-date=2014-08-05 \|archive-date=2014-08-08 \|archive-url=https://web.archive.org/web/20140808061650/http://dmblog.fico.com/2005/09/what_is_rete_ii.html \|url-status=dead }}</ref>

	===Rete-NT===		===Rete-NT===

imported>Prospector77: /* External links */ Noted long-gone link. Added an alternative.

2025-11-15T06:44:24Z

External links: Noted long-gone link. Added an alternative.

← Previous revision		Revision as of 06:44, 15 November 2025
Line 1:		Line 1:
	{{Short description\|Pattern matching algorithm}}		{{Short description\|Pattern matching algorithm}}
	{{More citations needed\|date=March 2018}}		{{More citations needed\|date=March 2018}}
	The '''Rete algorithm''' ({{IPAc-en\|ˈ\|r\|iː\|t\|iː}} {{respell\|REE\|tee}}, {{IPAc-en\|ˈ\|r\|eɪ\|t\|iː}} {{respell\|RAY\|tee}}, rarely {{IPAc-en\|ˈ\|r\|iː\|t}} {{respell\|REET}}, {{IPAc-en\|r\|ɛ\|ˈ\|t\|eɪ}} {{respell\|reh\|TAY}}) is a [[pattern matching]] [[algorithm]] for implementing [[rule-based system]]s. The algorithm was developed to efficiently apply many [[Rule of inference\|rules]] or patterns to many objects, or [[fact]]s, in a [[knowledge base]]. It is used to determine which of the system's rules should fire based on its data store, its facts. The Rete algorithm was designed by [[Charles Forgy\|Charles L. Forgy]] of [[Carnegie Mellon University]], first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper.<ref>{{cite journal \|last=Charles \|first=Forgy \|author-link=Charles Forgy \|title=Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem \|journal=[[Artificial Intelligence (journal)\|Artificial Intelligence]] \|date=1982 \|volume=19 \|pages=17–37 \|doi=10.1016/0004-3702(82)90020-0}}</ref>		The '''Rete algorithm''' ({{IPAc-en\|ˈ\|r\|iː\|t\|iː}} {{respell\|REE\|tee}}, {{IPAc-en\|ˈ\|r\|eɪ\|t\|iː}} {{respell\|RAY\|tee}}, rarely {{IPAc-en\|ˈ\|r\|iː\|t}} {{respell\|REET}}, {{IPAc-en\|r\|ɛ\|ˈ\|t\|eɪ}} {{respell\|reh\|TAY}}) is a [[pattern matching]] [[algorithm]] for implementing [[rule-based system]]s. The algorithm was developed to efficiently apply many [[Rule of inference\|rules]] or patterns to many objects, or [[fact]]s, in a [[knowledge base]]. It is used to determine which of the system's rules should fire based on its [[data store]], its facts. The Rete algorithm was designed by [[Charles Forgy\|Charles L. Forgy]] of [[Carnegie Mellon University]], first published in a working paper in 1974, and later elaborated in his 1979 Ph.D. thesis and a 1982 paper.<ref>{{cite journal \|last=Charles \|first=Forgy \|author-link=Charles Forgy \|title=Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem \|journal=[[Artificial Intelligence (journal)\|Artificial Intelligence]] \|date=1982 \|volume=19 \|pages=17–37 \|doi=10.1016/0004-3702(82)90020-0}}</ref>

	==Overview==		==Overview==
	A [[naïve algorithm\|naive implementation]] of an [[expert system]] might check each [[Rule of inference\|rule]] against known [[fact]]s in a [[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 naive approach performs far too slowly. The Rete algorithm provides the basis for a more efficient implementation. A Rete-based expert system builds a network of [[Vertex (graph theory)\|node]]s, where each node (except the root) corresponds to a pattern occurring in the left-hand-side (the condition part) 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 that satisfy that pattern. This structure is essentially a generalized [[trie]]. 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.		A [[naïve algorithm\|naive implementation]] of an [[expert system]] might check each [[Rule of inference\|rule]] against known [[fact]]s in a [[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 naive approach performs far too slowly. The Rete algorithm provides the basis for a more efficient implementation. A Rete-based expert system builds a network of [[Vertex (graph theory)\|node]]s, where each node (except the root) corresponds to a pattern occurring in the left-hand-side (the condition part) 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 that satisfy that pattern. This structure is essentially a generalized [[trie]]. 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.

	Rete was first used as the core engine of the [[OPS5]] production system language, which was used to build early systems including R1 for Digital Equipment Corporation. Rete has become the basis for many popular rule engines and expert system shells, including [[CLIPS programming language\|CLIPS]], [[Jess programming language\|Jess]], [[Drools]], [[IBM Operational Decision Management]], [[BizTalk]] [[Business rules engine\|Rules Engine]], [[Soar (cognitive architecture)\|Soar]], and [[Evrete]]. The word 'Rete' is Latin for 'net' or 'comb'. The same word is used in modern Italian to mean 'network'. Charles Forgy has reportedly stated that he adopted the term 'Rete' because of its use in anatomy to describe a network of blood vessels and nerve fibers.<ref>[http://www.sparklinglogic.com/rete-algorithm-demystified-part-1/ "Rete Algorithm Demystified! – Part 1"] by Carole-Ann Matignon</ref>		Rete was first used as the core engine of the [[OPS5]] production system language, which was used to build early systems including R1 for [[Digital Equipment Corporation]]. Rete has become the basis for many popular rule engines and expert system shells, including [[CLIPS programming language\|CLIPS]], [[Jess programming language\|Jess]], [[Drools]], [[IBM Operational Decision Management]], [[BizTalk]] [[Business rules engine\|Rules Engine]], [[Soar (cognitive architecture)\|Soar]], and [[Evrete]]. The word 'Rete' is Latin for 'net' or 'comb'. The same word is used in modern Italian to mean 'network'. Charles Forgy has reportedly stated that he adopted the term 'Rete' because of its use in anatomy to describe a network of blood vessels and nerve fibers.<ref>[http://www.sparklinglogic.com/rete-algorithm-demystified-part-1/ "Rete Algorithm Demystified! – Part 1"] by Carole-Ann Matignon</ref>

	The Rete algorithm is designed to sacrifice [[computer memory\|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 and server consumption problems. Other algorithms, both novel and Rete-based, have since been designed that require less memory (e.g. Rete<ref>{{cite web \|author1=Ian Wright \|author2=James Marshall \|title=The Execution Kernel of RC++: RETE A Faster Rete with TREAT as a Special Case \|url=http://www.cs.bris.ac.uk/Publications/Papers/2000091.pdf \|access-date=2013-09-13 \|archive-url=https://web.archive.org/web/20040725232722/http://www.cs.bris.ac.uk/Publications/Papers/2000091.pdf \|archive-date=2004-07-25 \|language=en-gb \|url-status=dead}}</ref> or Collection Oriented Match<ref>{{cite book \|author1=Anurag Acharya \|author2=Milind Tambe \|title=Proceedings of the second international conference on Information and knowledge management - CIKM '93 \|chapter=Collection Oriented Match \|year=1993 \|pages=516–526 \|chapter-url=http://teamcore.usc.edu/papers/1993/cikm-final.pdf \|publisher=CIKM '93 Proceedings of the second international conference on Information and knowledge management \|archive-url=https://web.archive.org/web/20120318073602/http://teamcore.usc.edu/papers/1993/cikm-final.pdf \|archive-date=2012-03-18 \|doi=10.1145/170088.170411\|isbn=0897916263 \|s2cid=5159932 }}</ref>).		The Rete algorithm is designed to sacrifice [[computer memory\|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 and server consumption problems. Other algorithms, both novel and Rete-based, have since been designed that require less memory (e.g. Rete<ref>{{cite web \|author1=Ian Wright \|author2=James Marshall \|title=The Execution Kernel of RC++: RETE A Faster Rete with TREAT as a Special Case \|url=http://www.cs.bris.ac.uk/Publications/Papers/2000091.pdf \|access-date=2013-09-13 \|archive-url=https://web.archive.org/web/20040725232722/http://www.cs.bris.ac.uk/Publications/Papers/2000091.pdf \|archive-date=2004-07-25 \|language=en-gb \|url-status=dead}}</ref> or Collection Oriented Match<ref>{{cite book \|author1=Anurag Acharya \|author2=Milind Tambe \|title=Proceedings of the second international conference on Information and knowledge management - CIKM '93 \|chapter=Collection Oriented Match \|year=1993 \|pages=516–526 \|chapter-url=http://teamcore.usc.edu/papers/1993/cikm-final.pdf \|publisher=CIKM '93 Proceedings of the second international conference on Information and knowledge management \|archive-url=https://web.archive.org/web/20120318073602/http://teamcore.usc.edu/papers/1993/cikm-final.pdf \|archive-date=2012-03-18 \|doi=10.1145/170088.170411\|isbn=0897916263 \|s2cid=5159932 }}</ref>).
Line 61:		Line 61:
	Some engines support advanced refraction strategies in which certain production instances executed in a previous cycle are not re-executed in the new cycle, even though they may still exist on the agenda.		Some engines support advanced refraction strategies in which certain production instances executed in a previous cycle are not re-executed in the new cycle, even though they may still exist on the agenda.

	It is possible for the engine to enter into never-ending loops in which the agenda never reaches the empty state. For this reason, most engines support explicit "halt" verbs that can be invoked from production action lists. They may also provide automatic [[cycle detection\|loop detection]] in which never-ending loops are automatically halted after a given number of iterations. Some engines support a model in which, instead of halting when the agenda is empty, the engine enters a wait state until new facts are asserted externally.		It is possible for the engine to enter into never-ending loops in which the agenda never reaches the empty state. For this reason, most engines support explicit "halt" verbs that can be invoked from production action lists. They may also provide automatic [[cycle detection\|loop detection]] in which never-ending loops are automatically halted after a given number of iterations. Some engines support a model in which, instead of halting when the agenda is empty, the engine enters a [[wait state]] until new facts are asserted externally.

	As for conflict resolution, the firing of activated production instances is not a feature of the Rete algorithm. However, it is a central feature of engines that use Rete networks. Some of the optimisations offered by Rete networks are only useful in scenarios where the engine performs multiple match-resolve-act cycles.		As for conflict resolution, the firing of activated production instances is not a feature of the Rete algorithm. However, it is a central feature of engines that use Rete networks. Some of the optimisations offered by Rete networks are only useful in scenarios where the engine performs multiple match-resolve-act cycles.
Line 125:		Line 125:
	The Rete algorithm is suited to scenarios where forward chaining and "inferencing" is used to calculate new facts from existing facts, or to filter and discard facts in order to arrive at some conclusion. It is also exploited as a reasonably efficient mechanism for performing highly combinatorial evaluations of facts where large numbers of joins must be performed between fact tuples. Other approaches to performing rule evaluation, such as the use of [[decision trees]], or the implementation of sequential engines, may be more appropriate for simple scenarios, and should be considered as possible alternatives.		The Rete algorithm is suited to scenarios where forward chaining and "inferencing" is used to calculate new facts from existing facts, or to filter and discard facts in order to arrive at some conclusion. It is also exploited as a reasonably efficient mechanism for performing highly combinatorial evaluations of facts where large numbers of joins must be performed between fact tuples. Other approaches to performing rule evaluation, such as the use of [[decision trees]], or the implementation of sequential engines, may be more appropriate for simple scenarios, and should be considered as possible alternatives.

	Performance of Rete is also largely a matter of implementation choices (independent of the network topology), one of which (the use of hash tables) leads to major improvements.		Performance of Rete is also largely a matter of implementation choices (independent of the [[network topology]]), one of which (the use of hash tables) leads to major improvements.
	Most of the performance benchmarks and comparisons available on the web are biased in some way or another. To mention only a frequent bias and an unfair type of comparison:		Most of the performance benchmarks and comparisons available on the web are biased in some way or another. To mention only a frequent bias and an unfair type of comparison:
	1) the use of toy problems such as the Manners and Waltz examples; such examples are useful to estimate specific properties of the implementation, but they may not reflect real performance on complex applications;		1) the use of toy problems such as the Manners and Waltz examples; such examples are useful to estimate specific properties of the implementation, but they may not reflect real performance on complex applications;
Line 142:		Line 142:

	===Rete-NT===		===Rete-NT===
	In 2010, Forgy developed a new generation of the Rete algorithm. In an InfoWorld benchmark, the algorithm was deemed 500 times faster than the original Rete algorithm and 10 times faster than its predecessor, Rete II.<ref>{{cite magazine\|last=Owen \|first=James \|url=http://www.infoworld.com/t/business-rule-management-systems/worlds-fastest-rules-engine-822 \|title=World's fastest rules engine \| Business rule management systems \|magazine=InfoWorld \|date=2010-09-20 \|access-date=2012-04-07}}</ref> This algorithm is now licensed to Sparkling Logic, the company that Forgy joined as investor and strategic advisor,<ref>{{cite web\|url=http://www.pr.com/press-release/365279 \|title=It's Official, Dr. Charles Forgy Joins Sparkling Logic as Strategic Advisor \|publisher=PR.com \|date=2011-10-31 \|access-date=2012-04-07}}</ref><ref>{{cite web\|url=http://www.sparklinglogic.com/advisors/ \|title=Dr. Charles Forgy, PhD \|publisher=www.sparklinglogic.com \|access-date=2012-04-07}}</ref> as the inference engine of the SMARTS product.		In 2010, Forgy developed a new generation of the Rete algorithm. In an [[InfoWorld]] benchmark, the algorithm was deemed 500 times faster than the original Rete algorithm and 10 times faster than its predecessor, Rete II.<ref>{{cite magazine\|last=Owen \|first=James \|url=http://www.infoworld.com/t/business-rule-management-systems/worlds-fastest-rules-engine-822 \|title=World's fastest rules engine \| Business rule management systems \|magazine=InfoWorld \|date=2010-09-20 \|access-date=2012-04-07}}</ref> This algorithm is now licensed to Sparkling Logic, the company that Forgy joined as investor and strategic advisor,<ref>{{cite web\|url=http://www.pr.com/press-release/365279 \|title=It's Official, Dr. Charles Forgy Joins Sparkling Logic as Strategic Advisor \|publisher=PR.com \|date=2011-10-31 \|access-date=2012-04-07}}</ref><ref>{{cite web\|url=http://www.sparklinglogic.com/advisors/ \|title=Dr. Charles Forgy, PhD \|publisher=www.sparklinglogic.com \|access-date=2012-04-07}}</ref> as the inference engine of the SMARTS product.

	===Rete-OO===		===Rete-OO===
	Considering that Rete aims to support [[first-order logic]] (basically [[if-then-else]] statements), Rete-OO<ref>{{Cite journal\|last1=Sottara\|first1=Davide\|last2=Mello\|first2=Paola\|author2-link=Paola Mello\|last3=Proctor\|first3=Mark\|year=2010\|title=A Configurable Rete-OO Engine for Reasoning with Different Types of Imperfect Information\|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.3826&rep=rep1&type=pdf\|format=PDF\|journal=IEEE Transactions on Knowledge and Data Engineering\|volume=22\|issue=11\|pages=1535–1548\|doi=10.1109/TKDE.2010.125\|citeseerx=10.1.1.713.3826\|archive-url=https://web.archive.org/web/20220110153745/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.3826&rep=rep1&type=pdf\|archive-date=2022-01-10\|access-date=2022-01-10\|s2cid=18895309}}</ref> aims to provide a rule-based system that supports uncertainty (where the information to make a decision is missing or is inaccurate). According to the author's proposal, the rule "''if Danger then Alarm''" would be improved to something such as "''given the probability of Danger, there will be a certain probability of hearing an Alarm''" or even "''the greater the Danger, the louder should be Alarm''". For this it extends the [[Drools]] language (which already implements the Rete algorithm) to make it support [[probabilistic logic]], like [[fuzzy logic]] and [[Bayesian network]]s.		Considering that Rete aims to support [[first-order logic]] (basically [[if-then-else]] statements), Rete-OO<ref>{{Cite journal\|last1=Sottara\|first1=Davide\|last2=Mello\|first2=Paola\|author2-link=Paola Mello\|last3=Proctor\|first3=Mark\|year=2010\|title=A Configurable Rete-OO Engine for Reasoning with Different Types of Imperfect Information\|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.3826&rep=rep1&type=pdf\|format=PDF\|journal=IEEE Transactions on Knowledge and Data Engineering\|volume=22\|issue=11\|pages=1535–1548\|doi=10.1109/TKDE.2010.125\|bibcode=2010ITKDE..22.1535S \|citeseerx=10.1.1.713.3826\|archive-url=https://web.archive.org/web/20220110153745/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.713.3826&rep=rep1&type=pdf\|archive-date=2022-01-10\|access-date=2022-01-10\|s2cid=18895309}}</ref> aims to provide a rule-based system that supports uncertainty (where the information to make a decision is missing or is inaccurate). According to the author's proposal, the rule "''if Danger then Alarm''" would be improved to something such as "''given the probability of Danger, there will be a certain probability of hearing an Alarm''" or even "''the greater the Danger, the louder should be Alarm''". For this it extends the [[Drools]] language (which already implements the Rete algorithm) to make it support [[probabilistic logic]], like [[fuzzy logic]] and [[Bayesian network]]s.

	== See also ==		== See also ==
Line 155:		Line 155:

	== External links ==		== External links ==
	* [http://drdobbs.com/184405218 Rete Algorithm explained] Bruce Schneier, Dr. Dobb's Journal		* [http://drdobbs.com/184405218 Rete Algorithm explained] Bruce Schneier, Dr. Dobb's Journal (Broken link)
	* [http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf Production Matching for Large Learning Systems – R Doorenbos] Detailed and accessible description of Rete, also describes a variant named Rete/UL, optimised for large systems (PDF)		* [http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf Production Matching for Large Learning Systems – R Doorenbos] Detailed and accessible description of Rete, also describes a variant named Rete/UL, optimised for large systems (PDF)
	* [http://www.cut-the-knot.org/classes/Last.shtml According to the Rules] (A short introduction from [[cut-the-knot]])		* [http://www.cut-the-knot.org/classes/Last.shtml According to the Rules] (A short introduction from [[cut-the-knot]])
			* [https://dmcommunity.org/wp-content/uploads/2016/06/rulesfest2009-terrill-anintrorete.pdf An Introduction to the Rete Algorithm]

	[[Category:Expert systems]]		[[Category:Expert systems]]
	[[Category:Pattern matching]]		[[Category:Pattern matching]]

2804:14C:5B87:5754:0:0:0:1512: /* Diagram */

2025-03-01T01:12:30Z

Diagram

Show changes

Rete algorithm - Revision history

imported>ShimmeringStones: /* growthexperiments-addlink-summary-summary:2|0|0 */

imported>Prospector77: /* External links */ Noted long-gone link. Added an alternative.

2804:14C:5B87:5754:0:0:0:1512: /* Diagram */