On Oct 9, 2007, at 3:42 AM, Mike Stacey wrote:
Just wondering if the paper by Forgy "Rete: A Fast Algorithm for
the Many Pattern/Many Object Pattern Match Problem," Artficial
Intelligence, vol. 19, pp. 17-37, 1982 is relevant to the version
of Rete used in Jess in terms of time complexity?
I'm mainly interested in the time complexity of jess. The above
paper states worst case time for a rule firing is O(W^(2P-1)) where
W is number of elements (facts) in working memory and C is number
of patters in the rule. Is this the same for Jess?
Hi Mike,
Rete is a tough algorithm to analyze. There were other papers
published after Forgy's that tried to do it more rigorously, but the
thing is that the analysis depends on the rules your write and the
data you use. The "worst case" happens only when you write the worst
possible rules and use the worst possible data and the worst possible
implementation of Rete, and at least the first of these is completely
under your control, so it doesn't really happen.
For Jess, "W" is never really the total number of facts, but rather
the number of facts from any given template, and the power is
virtually never anywhere near the worst case. Most pattern matching
is done in linear time or better w.r.t. the size of working memory.
The worst case exponent is essentially P, not 2P-1, and if you run
into this situation, you can generally optimize your rules to avoid it.
If you look in the FAQ (http://www.jessrules.com/FAQ.shtml) at the
question "Why is my program so slow?" you'll see the classic example
of a rule that really does perform like W^P, and a discussion of how
to rewrite it to avoid this behavior.
---------------------------------------------------------
Ernest Friedman-Hill
Informatics & Decision Sciences Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
PO Box 969, MS 9012 [EMAIL PROTECTED]
Livermore, CA 94550 http://www.jessrules.com
--------------------------------------------------------------------
To unsubscribe, send the words 'unsubscribe jess-users [EMAIL PROTECTED]'
in the BODY of a message to [EMAIL PROTECTED], NOT to the list
(use your own address!) List problems? Notify [EMAIL PROTECTED]
--------------------------------------------------------------------
