DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA278979
Title:
Combining Left and Right Unlinking for Matching a Large Number of Learned Rules
Corporate Author:
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Report Date:
1994-04-04
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.
Descriptive Note:
Research rept.
Supplementary Note:
Supported in conjunction with DARPA. DOI: 10.21236/ADA278979
Pages:
0018
Distribution Statement:
Approved for public release; distribution is unlimited.
Contract Number:
F33615-93-1-1330
File Size:
1.05MB
