On the Performance of Lazy Matching in Production Systems

Daniel P. Miranker, David A. Brant, Bernie Lofaso, David Gadbois

Production systems are an established method for encoding knowledge in an expert system. The semantics of production system languages and the concomitant algorithms for their evaluation, RETE and TREAT, enumerate the set of rule instantiations and then apply a strategy that selects a single instantiation for firing. Often rule instantiations are calculated and never fired. In a sense, the time and space required to eagerly compute these unfired instantiations is wasted. This paper presents preliminary results about a new match technique, lazy matching. The lazy match algorithm folds the selection strategy into the search for instantiations, such that only one instantiation is computed per cycle. The algorithm improves the worst-case asymptotic space complexity of incremental matching. Moreover, empirical and analytic results demonstrate that lazy matching can substantially improve the execution time of production system programs.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.