Rete Algorithm

The Rete algorithm is a pattern-matching algorithm built for rule-based expert systems, designed to efficiently determine which of many stored rules should fire against a large and constantly changing set of facts in a knowledge base, without re-testing every rule against every fact from scratch each time the facts change. It works by compiling the conditions of all the rules into a shared network of nodes, so that as a fact is added, removed or changed it is propagated once through the network, is stored in intermediate memory nodes where it partially matches a rule's conditions, and triggers that rule only once all of its conditions have been satisfied by the current set of facts. This network structure trades additional memory for a large reduction in repeated computation, commonly delivering performance many times faster than a naive rule-checking approach on systems with large rule sets. Charles Forgy developed the algorithm at Carnegie Mellon University, first publishing it in 1974 and elaborating it in his 1979 doctoral dissertation and a widely cited 1982 paper; its name is Latin for net, chosen for the same reason anatomists use the word to describe a network of blood vessels or nerves.