Encyclopedia > Rete algorithm

  Article Content

Rete algorithm

The Rete algorithm is an efficient algorithm for implementing rule-based ("expert") systems. The Rete algorithm was designed by Dr. Charles L. Forgy of Carnegie Mellon University in 1979 (see his paper "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem", Artificial Intelligence, 19, pp 17-37, 1982). Rete has become the basis for many popular expert systems, including OPS5, CLIPS[?], JESS[?], and LISA.

A naive implementation of an expert system might check each rule against the known facts in the database, 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 databases, this naive approach performs far too slowly.

The Rete algorithm (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 occuring 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 naive 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.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Kings Park, New York

... The average household size is 2.86 and the average family size is 3.32. In the town the population is spread out with 25.2% under the age of 18, 5.7% from 18 to 24, ...

 
 
 
This page was created in 39.8 ms