Combining Left and Right Unlinking for Matching a Large Number of Learned Rules
Abstract
In systems which learn a large number of rules (productions), it is important to match the rules efficiently, in order to avoid the machine learning utility problem -- if the learned rules slow down the matcher, the 'learning' can slow the whole system down to a crawl. So we need match algorithms that scale well with the number of productions in the system. Right unlinking was introduced as a way to improve the scalability of the Rete match algorithm. In this paper we build on this idea, introducing a symmetric optimization, left unlinking, and demonstrating that it makes Rete scale well on an even larger class of systems. Unfortunately, when left and right unlinking are combined in the same system, they can interfere with each other. We give a particular way to combine them which we prove minimizes the interference, and analyze the worst- case remaining interference. Finally, we present empirical results showing that the interference is very small in practice, and that the combination of left and right unlinking allows five of our seven testbed systems to learn over 100,000 rules without incurring a significant increase in match cost.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 04, 1994
- Accession Number
- ADA278979
Entities
People
- Robert B. Doorenbos
Organizations
- Carnegie Mellon University