Editing Rete algorithm (section)

==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.

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>).