Forgy, C.

Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem


The Rete Match Algorithm is an efficient method for comparing a large collection of patterns to a large collection of objects. It finds all the objects that match each pattern. The algorithm was developed for use in production system interpreters, and it has been used for systems containing from a few hundred to more than a thousand patterns and objects. It explains the basic concepts of the algorithm, it describes pattern and object representations that are appropriate for the algorithm, and it describes the operations performed by the pattern matcher.

OPS5 user’s manual


These productions operate on expressions stored in a global data base called working memory. The production system interpreter executes a production system by performing a sequence of operations called the recognize-act cycle: 1. The element would be (block tname blockl tcolor red tmass 500 tlength,100 twidth 100 theight 100) As this shows, an element consists of a class name (bl ock in this case) followed by some number of attributes and values, with everything enclosed in parentheses. Thus the pattern (block tcolor red) would match the working memory element (block tname blockl tcolor red tmass 500 tlength 100 twidth 100 theight 100) Another way a pattern can be an abstraction of a working memory element is to contain incompletely specified values.