Editing Rete algorithm (section)

== Alternatives ==

=== Alpha Network ===

A possible variation is to introduce additional memories for each intermediate node in the discrimination network.   This increases the overhead of the Rete, but may have advantages in situations where rules are dynamically added to or removed from the Rete, making it easier to vary the topology of the discrimination network dynamically.

An alternative implementation is described by Doorenbos.<ref>[http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf Production Matching for Large Learning Systems] from SCS Technical Report Collection,
School of Computer Science, Carnegie Mellon University</ref> In this case, the discrimination network is replaced by a set of memories and an index.    The index may be implemented using a [[hash table]].   Each memory holds WMEs that match a single conditional pattern, and the index is used to reference memories by their pattern.   This approach is only practical when WMEs represent fixed-length tuples, and the length of each tuple is short (e.g., 3-tuples).   In addition, the approach only applies to conditional patterns that perform [[Equality (mathematics)|equality]] tests against [[Variable (mathematics)|constant]] values. When a WME enters the Rete, the index is used to locate a set of memories whose conditional pattern matches the WME attributes, and the WME is then added directly to each of these memories. In itself, this implementation contains no 1-input nodes. However, in order to implement non-equality tests, the Rete may contain additional 1-input node networks through which WMEs are passed before being placed in a memory. Alternatively, non-equality tests may be performed in the beta network described below.

=== Beta Network ===

A common variation is to build [[linked list]]s of tokens where each token holds a single WME. In this case, lists of WMEs for a partial match are represented by the linked list of tokens. This approach may be better because it eliminates the need to copy lists of WMEs from one token to another. Instead, a beta node needs only to create a new token to hold a WME it wishes to join to the partial match list, and then link the new token to a parent token stored in the input beta memory. The new token now forms the head of the token list, and is stored in the output beta memory.

Beta nodes process tokens. A token is a unit of storage within a memory and also a unit of exchange between memories and nodes.  In many implementations, tokens are introduced within alpha memories where they are used to hold single WMEs. These tokens are then passed to the beta network.

Each beta node performs its work and, as a result, may create new tokens to hold a list of WMEs representing a partial match. These extended tokens are then stored in beta memories, and passed to subsequent beta nodes. In this case, the beta nodes typically pass lists of WMEs through the beta network by copying existing WME lists from each received token into new tokens and then adding further WMEs to the lists as a result of performing a join or some other action. The new tokens are then stored in the output memory.