A fast pattern-matching algorithm using matching candidates for production systems

Abstract

Several fast pattern matching algorithms have been proposed to improve the inference speed of production systems. In almost all of these algorithms, conditions in rules are represented using a dataflow network and working memory elements propagates this network as tokens. These algorithms are effective, but excessive constant testing is unavoidable when the working memory must be frequently updated.

This paper proposes a faster pattern matching algorithm for production systems. It uses an improved inference network employing matching candidates to circumvent the constant testing inherent in conventional networks. We classify constant-test nodes into inter-pattern test nodes and intra-pattern test nodes, a distinction not made in conventional networks. We then introduce memory nodes for matching candidates between these test nodes. This is done in order to exclude patterns that do not to be fired quickly. The ID3 algorithm is used to make an efficient inter-pattern test network that is capable of finding patterns in the rule conditions for working memory elements.