Rete algorithm
The Rete algorithm ( Latin rete , network, network) is an algorithm and expert system for pattern recognition and for mapping system processes using rules. It was developed by the US computer scientist Charles Forgy as part of his doctoral thesis at Carnegie Mellon University , which should lead him to the title in 1979. The algorithm is free because the US Department of Defense was sufficiently involved in its creation.
Goals of the algorithm
The Rete algorithm was developed with a view to ensuring very efficient rule processing. In addition, large rule sets can still be handled efficiently. In its development it was superior to the existing systems by a factor of 3000.
Use and variations
Nowadays, RETE forms the basis for many control systems such as B. various Prolog interpreters or so-called Business Rules Engines , and has established itself as the de facto standard for these .
So far there are two direct descendants Rete II and Rete III. Both are about 50 times faster than the original approach. Rete III includes a few enhancements that slightly increase its efficiency. The development was closely based on the DEC XCON platform and was initially implemented in OPS systems , especially in OPS2 and later in OPS5. Savings in the millions were named. The implemented set of rules had around 10,000 elements in the final stage.
Drools is an example of a business rule engine based on the Rete algorithm. In the meantime (from version 6.0) a successor algorithm (PHREAK) is active in Drools.
disadvantage
The high speed of the algorithm is at the expense of the memory used.
Individual evidence
- ^ Charles Forgy: Rete: A Fast Algorithm for the Many Pattern / Many Object Pattern Match Problem. In: Artificial Intelligence, vol. 19, pp. 17-37, 1982.
- ↑ Lecture script on the Rete algorithm (PDF; 86 kB)
- ↑ Lars Wunderlich: Java Rules Engines. Development of rule-based systems. developer.press, Frankfurt / Main 2006, ISBN 3-935042-75-2 .
- ↑ Website of the business rule engine Drools