Paper Title
Efficient Matching Based on Bipartite Graph for Inference Engine

Inference engine is a core component of expert system, and its main task is efficient matching of the rules against incoming facts. Usually the most of the execution time of match-resolve-execute reasoning cycle is consumed by the matching operation of the rule set. The popular matching schemes including Rete algorithm require to load the rules before the matching operation begins causing large match time. To overcome this issue, this paper presents a scheme utilizing bipartite graph where the premise and consequence of each rule are mapped to the partitioned nodes. Also, each edge in the graph is assigned a weight representing the association degree between the nodes. The weighted edges maximize the efficiency matching without building a rete tree and memory. MATLAB simulation reveals that the proposed scheme allows consistently smaller match time than Rete regardless of the number of rules. Keywords - Bipartite graph, Rule matching, Inference engine, Expert system