Rete

Latin for network.

A specialized graph data structure used in expert system shells and production systems, such as CLIPS and Jess.

[ ... give overview of details ... ]

[ Beta/Alpha nodes... node memory ... many object/many match ...]

[ ... Original Forgy article in Artificial Intelligence Journal ... ]

The citation for the original article is:

C. Forgy, RETE: A fast algorithm for the many pattern/many object pattern match problem, Artificial Intelligence, 19 (1982), pp 17-37.

Unfortunately, you can't get this article anywhere on-line. You'll have to trawl your local University Library.


Here is a paper comparing RETE and TREAT that is available on-line http://citeseer.nj.nec.com/nayak88comparison.html


lexfiend 20 Oct 2005: Also see Wikipedia [L1 ] for a short summary and links to other resources. I found Bob Doorenbos's PhD thesis particularly readable (first external link in the Wikipedia page, or [L2 ]).

In addition, the Drools project has a page [L3 ] dedicated to Rete-related papers, including the original Forgy one (which is available on-line, but for a fee).

NEM 21 Oct 2005: I did some research a few years ago on Rete and production systems. The most recent algorithm I am aware of is RETE*:

Ian Wright and James Marshall, "The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case". International Journal of Intelligent Games and Simulation, 2(1). pp36-48, Feb 2003. [L4 ]

There is also "leaps" by the same author as Treat, which is a lazy algorithm, from what I remember, that uses knowledge about the conflict resolution strategy to optimise the matching process. My own modest contribution to the literature is the following paper that describes some simple optimisations implemented in Gore (which is still waiting for me to have a spare week or so to finish off):

Neil Madden (2003). “Optimising RETE for low-memory, multiagent systems” — in Proceedings of Game-On 2003: 4th International Conference on Intelligent Games and Simulation, pp 77–81, London, November 2003. [L5 ]

TclCLIPS provides Tcl access to CLIPS, which is based on a Rete implementation.