The Rete Matching Algorithm (2002)

I've become mildly obsessed with the potential applications of that behavior, and one of my favorite ideas (of which I'm mostly unqualified to implement) is a compiler super-optimizer, storing the rewriting rules as individual rules in the rule engine. This would also allow for adding interesting optimizations that might be purposefully omitted from existing optimizing compilers due to their infrequent or expensive matching. It would also allow for optimizations anywhere in the compiler pipeline without having to worry much about modularity, which could open up the possibility of macro-level optimizations at the AST level (for example, rewriting an array of objects as an object of arrays to speed up folds and maps over the array), or the machine code level (taking advantage of small differences in instruction sets and other on-die resources).

That being said, I'm pretty sure the existing Rete implementations are poorly suited to matching on subtrees as would probably be required for this type of optimization, and the memory requirements would mean compilation would likely need to be done on servers. Tradeoffs aplenty, but I would still love to see it happen.

OPS5 was very hackable. For one project I modified the Rete algorithm to support multiple data worlds. Fun times!

I think our modern languages with fast interpreters or compilers are a better route. The O(1) point saosebastiao brought up was a nice benefit. It does bring clarity as another commenter said. So, if we use it, probably best to use it selectively as a DSL in a LISP or ML language.

Note: The author's name was a surprise, too. I didn't realize Bruce wrote on that topic.

https://en.m.wikipedia.org/wiki/CLIPS

my very first consulting project (yes, i had absolutely no experience), around that time, was implementing blaze advisor (now owned by fico: http://www.fico.com/en/products/fico-blaze-advisor-decision-...) to migrate a mainframe-based automated life underwriting system to a j2ee client/server system.

performance was a major concern, so i read Forgy's 1982 paper about RETE (that i didn't quite understand frankly), but the key takeaway (for me at least) was that all the hard work happened during compilation so running performance shouldn't be an issue. from what i dimly remember, the algorithm iterates through the rules set building something akin to a decision tree until the tree reaches a stable state. if it never reaches stability, it will throw a compile error. once the tree is built, matching is very fast.

the holy grail was that "business analysts" (remember when that title was in vogue? =) could write the rules, saving you months of precious time and thousands of dollars by not paying programmers (it did not turn out that way of course).

https://github.com/rururu/rete4frames

The team then continued with a new programming language, YES/L1. Using DeRemer's LALR work in parsing, YES/L1 was a preprocessor to IBM's language PL/I. The language had extensions for expert system rules, and that was based on the RETE algorithm.

We IBM made YES/L1 an IBM Program Product, their highest quality software product category, with name KnowledgeTool.

Our team worked with GM to make a deployment. We wrote several papers and gave one at an AAAI IAAI conference at Stanford.

The work continued with Resource Object Data Manager (RODM). The role of RODM was automation for system and network monitoring and management.

So, RODM was some active storage that sat between (A) some target systems in a network or server farm and (B) some managing systems for the target systems.

For this work, RODM permitted building software objects. The objects were in an inheritance hierarchy. Each object had fields for data and methods with code. The intention was that the code would be rules written in KnowledgeTool.

The objects in RODM were dynamic in that they could be changed, say, roughly like files and directories in a traditional hierarchical file system, during execution. There was use of

Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, 'Extendible hashing—a fast access method for dynamic files', "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344.

for keeping track of the names and Cartesian trees for dynamic storage management.

RODM had transactional integrity with automatic deadlock detection and resolution.

The role of RODM was (A) have a place to write software for system and network automation, (B) have tools, infrastructure, etc. such code needed readily available, (C) be able to write code using expert system rules, e.g., in KnowledgeTool, (D) present to the writer of rules and code an automatically up to date object model of the target systems, (D) via the transactional integrity, etc., have coordination among several rules and several systems much as in relational database.

The most common approach to monitoring was use of thresholds on variables one at a time.

Such monitoring is necessarily essentially a continually applied statistical hypothesis test with null hypothesis that the system is healthy and a detection of a problem is essentially the same as rejection of that null hypothesis.

Well, to have a more powerful test, that is, better combinations of rates of false alarms and missed detections, it would be good to have the tests be multi-dimensional, that is, consider several variables jointly instead of separately and independently. So, wanted some statistical hypothesis tests that were multi-dimensional.

Next, commonly in statistical hypothesis testing, know the probability distribution of the data under the null hypothesis, but there have been tests that were distribution-free, that is, that made no assumptions about probability distributions. For the work in system monitoring and management, with multi-dimensional data, distribution-free tests were essential since in practice finding the distributions of multi-dimensional data was hopeless.

So, needed some statistical hypothesis tests that were both multi-dimensional and distribution-free. So, invented some.

The intention was that such hypothesis tests would commonly be better means of problem detection than the usual rule left hand sides, i.e.,

     When CPU_busy > 90% AND 
     paging_rate > 100 AND

An intention was that rules written in KnowledgeTool would run in RODM.

The RETE algorithm was used in a project for some work in artificial intelligence expert systems for server farm and network monitoring and management at the IBM Watson lab in Yorktown Heights.

The work started with the programming language OPS5.

Then the project invented a new programming -- language Yorktown Expert System Language 1, YES/L1. This language was a pre-processor to IBM's programming language PL/I. The pre-processing made use of the DeRemer LALR parsing tools. So, YES/LI was compiled.

And YES/LI had extensions for artificial intelligence expert systems based on the C. Forgy RETE algorithm and its working memory.

IBM shipped YES/L1 as the IBM Program Product KnowledgeTool.

Applying KnowledgeTool, we did joint work with GM.

We published several papers and gave one at a Stanford conference of the AAAI IAAI on Innovative Applications of Artificial Intelligence.

The work of the project continued with Resource Object Data Manager (RODM). RODM was more infrastructure for monitoring and management of server farms and networks.

The architectural idea of RODM was:

managing systems <--> RODM <--> managed systems

where the <--> is for two-way communications.

So, the role of RODM in the middle was something like the role of relational database between an applications program and a computer operating system file system, that is, to provide infrastructure, functionality, and tools to make the work easier, better organized, more reliable, etc.

Or, the managing systems didn't communicate directly with the managed systems but only through RODM.

So, in particular, RODM had, similar to relational database, transactional integrity. Also RODM had monotone locking protocol with automatic deadlock detection and resolution with roll-back and restart, etc.

RODM was object-oriented with an inheritance hierarchy. Each RODM object had data fields and also methods. Some of the methods were change methods and would fire (execute) when an associated field changed.

The object hierarchy was not static but was dynamic, that is, could change during execution, that is, during real-time monitoring and management. Or, the hierarchy was dynamic something like an operating system hierarchical file system that could change during execution of the operating system.

So, to keep track of the names in the object hierarchy, there was use of

Ronald Fagin, Jurg Nievergelt, Nicholas Pippenger, H. Raymond Strong, 'Extendible hashing—a fast access method for dynamic files', "ACM Transactions on Database Systems", ISSN 0362-5915, Volume 4, Issue 3, September 1979, Pages: 315 - 344.

The associated dynamic storage management was based on Cartesian trees.

The intention was that the methods could be written in rules in KnowledgeTool.

So, broadly, at the architectural level, RODM presented to the managing systems a model of, abstractions of, the managed systems with infrastructure, tools, handling the real-time aspects, coordination, e.g., via transactional integrity, etc.

Later RODM was shipped as part of IBM's NetView systems management product.

The most common approach to system monitoring was thresholds on variables with values from the managed systems, say, CPU busy, page faults per second, disk storage used, database transactions per second, network data rate.

Then essentially necessarily, monitoring with such variables is a case of statistical hypothesis tests with rates of false positives (false alarms, Type I error) and false negatives (missed detections, Type II error).

Here what statistical hypothesis testing calls the null hypothesis is an assumption that the target system being monitored is healthy, and when the hypothesis test rejects the null hypothesis is a detection of something wrong with the target system.

Such a statistical hypothesis test has higher power, such system monitoring has higher quality, when, for a given rate of false alarms, the rate of missed detections is lower, that is, the detection rate of real problems is higher.

In principle the quality can be improved by processing the variables jointly instead of separately. For this, we need a statistical hypothesis test that is multi-dimensional. Commonly a statistical hypothesis test knows and exploits the probability distribution of the input data assuming that the system is healthy (the conditional distribution given that the system is healthy). Alas, in the context of system monitoring and management, with multi-dimensional data, in practice, knowing this probability distribution is asking too much. So, we need statistical hypothesis tests that are distribution-free, that is, that make no assumptions about probability distributions.

So, for improving the methods in the objects in RODM for system monitoring, I invented a large collection of such statistical hypothesis tests that were both multi-dimensional and distribution-free.

So, in the sense of rules, expert systems, and the RETE algorithm, might change a rule from

     When CPU_busy > 95% AND paging_rate >
     100 AND transaction_rate < 10 Then
     system_thrashing = TRUE;

So, in this way are doing what has been called behavioral monitoring where we look for what is unusual.

At

http://www.sans.org/resources/idfaq/behavior_based.php

is

"IDFAQ: What is behavior based Intrusion Detection?"

by Herve Debar, IBM Zurich Research Laboratory with

"Therefore, the intrusion detection system might be complete (i.e. all attacks should be caught), but its accuracy is a difficult issue (i.e. you get a lot of false alarms)."

Well, commonly with a statistical hypothesis test and with the tests I invented, we get to select the false alarm rate in advance, in small steps over a wide range, and get that rate essentially exactly in practice. So, such tests solve the problem of

"you get a lot of false alarms".

That is, can set the false alarm rate as low as one pleases and get that rate in practice.