KRHyper Performance Evaluation

Application Extract: Transitive Closure

A fact base of 16470 facts with a single binary predicate. The facts contain nested terms, but are ground. The problem is to compute the transitive closure, which has 217439 facts.

Results

All results were obtained on a 2400 MHz Pentium computer.

• KRHyper can perform this in 17 seconds, requiring 63 megabytes of memory.
• If the values are represented as constants instead of nested terms, KRHyper need 8 seconds.
• Otter needs 37 minutes and 124 megabytes. Positive Hyperresolution was used as inference rule and the fact base formed the set of support, such that Otter operates similar to KRHyper, except that it does not perform rule application in the bulk-wise manner of semi-naive evaluation.
• Satchmo Compiler needs 2:14 hours and 271 megabytes, with default settings under SWI-Prolog.
• An experiment with Smodels (values were represented as constants) was aborted when the lparse preprocessor consumed all available memory.

Data

• Fact base references.tme.gz
• Definition of the transitive closure and option settings for KRHyper tc.tme