file.pdf (1.43 MB)
Transforming conjunctive match into RETE : a call-graph caching approach
journal contributionposted on 1998-01-01, 00:00 authored by Mark W. Perlin
Abstract: "Conjunctive match is often used in Artificial Intelligence as the kernel of a pattern-directed inference  engine. Conjunctive match entails generating and testing all possible combinations of objects against a pattern of constraints. While simple to program, it is an expensive, exponential cost computation. To reduce this average match cost in production system engines, the RETE match algorithm  was devised. RETE compiles each rule's pattern of constraints into a network, and then incrementally updates partial matches as objects are inserted and deleted. RETE, however, has its own cost: conceptual and implementational complexity.Call-graph caching (CGC)  is a mechanism for transforming recursive specifications into highly optimized networks. In this paper, we describe CGC, and use it to transform a family of recursive conjunctive match formulations into their corresponding RETE networks. Our approach illustrates the ideas behind RETE, and shows their application to other algorithms."