OBO-Edit:Reasoner Benchmarks: Difference between revisions

From GO Wiki
Jump to navigation Jump to search
No edit summary
 
(22 intermediate revisions by 2 users not shown)
Line 7: Line 7:
=== oboedit_fcr ===
=== oboedit_fcr ===


OBO-Edit Forward Chaining Reasoner. Fast, but only uses the following rules:
[[OBO-Edit:Forward Chaining Reasoner]] (LPR). Fast, but only uses the following rules:


* Transitivity
* Transitivity
Line 17: Line 17:
=== oboedit_lpr ===
=== oboedit_lpr ===


LinkPileReasoner (LPR). Successor to FCR.
[[OBO-Edit:Link Pile Reasoner]] (LPR). Successor to FCR.


Rules:
Rules:
Line 32: Line 32:
=== oboedit_rbr ===
=== oboedit_rbr ===


RuleBasedReasoner. Successor to LPR.
[[OBO-Edit:Rule Based Reasoner]] (RBR). Successor to LPR.


* Transitivity
* Transitivity
Line 53: Line 53:
Note that OWL reasoners will not allow you to ask questions of the form "what is the heart ventricle part_of?". To allow this we perform an extra step of materializing all transitive relation x class pairs (e.g. "heart part"). This leads to worse performance.
Note that OWL reasoners will not allow you to ask questions of the form "what is the heart ventricle part_of?". To allow this we perform an extra step of materializing all transitive relation x class pairs (e.g. "heart part"). This leads to worse performance.


The two main open source OWL reasoners are FaCT++ and Pellet
The two main open source OWL reasoners are FaCT++ and Pellet.
 
Note: even though the table below gives the suffix ".obo", each reasoner was executed on an owl file. These were generated by go2owl whenever the native form of the ontology is obo. If the source is owl then blipkit is used for the reverse translations. See [http://www.berkeleybop.org/obo-conv.cgi obo-conv]. NOTE THAT THIS GIVES AN ADVANTAGE TO OBO REASONERS AS SOME AXIOMS WILL BE DROPPED.


=== owlapi_pellet ===
=== owlapi_pellet ===
Line 74: Line 76:


Pellet 2.0 executed directly
Pellet 2.0 executed directly
=== hermit ===
Hermit 0.9.2 executed directly.
Note that hermit does not support object property chains -i.e. [[transitive_over]] or arbitrary [[Relation_composition]]. It will fail on any ontology that includes these. This means a lot of entries are blank.


=== oboedit_pwr ===
=== oboedit_pwr ===
Line 113: Line 121:
=== blipkit ===
=== blipkit ===


Backed by a prolog database
Backed by a prolog database. This is the same reasoner used in [http://www.berkeleybop.org/obol obol].See [http://www.blipkit.org blipkit home page]


* Transitivity
* Transitivity
Line 122: Line 130:
* Relation intersections
* Relation intersections
* Arbitrary rules
* Arbitrary rules


== Results ==
== Results ==
Line 131: Line 138:


=== Ontologies Used ===
=== Ontologies Used ===
TODO: show expressivity of each


The following ontologies were used:
The following ontologies were used:
Line 146: Line 155:
* fma2.obo
* fma2.obo
* go.obo
* go.obo
* go_xp_i.obo -- all GO internal xps. See [[Category:Internal_Cross_Products]]
* go_xp_i.obo -- all GO internal xps. See [[:Category:Internal_Cross_Products]]
* go_xp_r.obo -- [[XP:biological_prcess_xp_regulation]]
* go_xp_r.obo -- [[XP:biological_prcess_xp_regulation]]
* hp_xp.obo -- [http://www.berkeleybop.org/ontologies/#human_phenotype_xp]
* hp_xp.obo -- [http://www.berkeleybop.org/ontologies/#human_phenotype_xp]
Line 161: Line 170:
=== Preliminary Benchmarks ===
=== Preliminary Benchmarks ===


Blank = program did not complete in allotted time or ran out of memory (note: a few blanks remain to be filled in, programs did not complete for external reasons, this is PRELIMINARY!!)
'''THESE RESULTS ARE PRELIMINARY'''
 
Blank = program did not complete in allotted time (1-2hrs, varies) OR ran out of memory/heap OR possibly for other reasons, including bugs in my code. At this time, these results should be taken with a pinch of salt.
 
Also make sure you understand everything above before interpreting. OBO reasoners may have some unfair advantages here.


{|class="wikitable" style="text-align:center" border="1"
{|class="wikitable" style="text-align:center" border="1"
|-
|-
! ONT
! ONT
! hermit
! oboedit_fcr
! oboedit_fcr
! owlapi_pellet_mr
! owlapi_pellet_mr
Line 179: Line 193:
! blipkit
! blipkit
|-
|-
| DC_CL.obo
| [http://oboedit.org/reasoner-benchmarks/DC_CL.obo DC_CL]
| 0.154
| 0.096
| 0.096
| 3.26185
| 3.26185
| 0.321088
| 0.321088
| 0.269457
| 0.269457
| 0.125779
| 0.101434
|  
| 21
|  
|  
| 0.344787
| 0.344787
Line 193: Line 208:
| 0.04
| 0.04
|-
|-
| bp_xp_cc.obo
| [http://oboedit.org/reasoner-benchmarks/bp_xp_cc.obo bp_xp_cc]
|
| 13.476
| 13.476
|  
|  
|  
|  
| 113.021307
| 113.021307
| 54.366712
| 46.33769
|  
| 1668
|  
|  
|  
|  
Line 207: Line 223:
| 80.96
| 80.96
|-
|-
| bp_xp_cl.obo
| [http://oboedit.org/reasoner-benchmarks/bp_xp_cl.obo bp_xp_cl]
|
| 13.589
| 13.589
|  
|  
|  
|  
| 84.450377
| 84.450377
| 54.120796
| 49.550078
|  
| 1774
|  
|  
|  
|  
Line 221: Line 238:
| 89.41
| 89.41
|-
|-
| bp_xp_u.obo
| [http://oboedit.org/reasoner-benchmarks/bp_xp_u.obo bp_xp_u]
|
| 14.096
| 14.096
|  
|  
|  
|  
| 102.442893
| 102.442893
| 59.710887
| 52.879202
|  
| 2043
|  
|  
|  
|  
Line 235: Line 253:
| 86.89
| 86.89
|-
|-
| caro.obo
| [http://oboedit.org/reasoner-benchmarks/caro.obo caro]
| 0.038
| 0.018
| 0.018
| 0.234596
| 0.234596
| 0.013313
| 0.013313
| 0.031378
| 0.031378
| 0.026605
| 0.027466
|  
| 0
| 1.449529
| 1.449529
| 0.035096
| 0.035096
Line 249: Line 268:
| 0.01
| 0.01
|-
|-
| cc_xp_i.obo
| [http://oboedit.org/reasoner-benchmarks/cc_xp_i.obo cc_xp_i]
|
| 13.36
| 13.36
|  
|  
|  
|  
| 65.882047
| 65.882047
| 283.275332
| 289.564573
|  
| 1573
|  
|  
|  
|  
Line 261: Line 281:
|  
|  
| 1407
| 1407
| 67.05
|-
| [http://oboedit.org/reasoner-benchmarks/cc_xp_p.obo cc_xp_p]
|  
|  
|-
| cc_xp_p.obo
| 0.92
| 0.92
|  
|  
| 161.977906
| 161.977906
| 19.044575
| 19.044575
| 1.905131
| 1.914166
| 148
| 148
|  
|  
Line 277: Line 298:
| 3.59
| 3.59
|-
|-
| cell.obo
| [http://oboedit.org/reasoner-benchmarks/cell.obo cell]
| 0.212
| 0.391
| 0.391
| 3.015834
| 3.015834
| 0.17246
| 0.17246
| 2.024176
| 2.024176
| 1.025127
| 1.039019
|  
| 32
| 45.124648
| 45.124648
| 7.315394
| 7.315394
Line 291: Line 313:
| 1.14
| 1.14
|-
|-
| fly.obo
| [http://oboedit.org/reasoner-benchmarks/chebt.obo chebt]
| 9.156
|
| 105.981208
| 125.216634
|
| 180.321342
| 2881
|
|
| 100.201565
| 10
| 4927
|
|-
| [http://oboedit.org/reasoner-benchmarks/fly.obo fly]
| 2.847
| 4.122
| 4.122
| 43.970665
| 43.970665
| 1.678357
| 1.678357
| 23.575053
| 23.575053
| 11.259419
| 10.96353
|  
| 330
|  
|  
| 685.638543
| 685.638543
Line 305: Line 343:
| 18.81
| 18.81
|-
|-
| fly_xp.obo
| [http://oboedit.org/reasoner-benchmarks/fly_xp.obo fly_xp]
| 5.514
| 10.223
| 10.223
| 5.514895
| 5.514895
| 0.393729
| 0.393729
| 31.695978
| 31.695978
| 24.125094
| 22.514039
| 522
| 526
|  
|  
| 0.390108
| 0.390108
Line 319: Line 358:
| 24.02
| 24.02
|-
|-
| fma2.obo
| [http://oboedit.org/reasoner-benchmarks/fma2.obo fma2]
| 11.857
| 33.16
| 33.16
| 156.072801
| 156.072801
Line 325: Line 365:
| 157.908895
| 157.908895
|  
|  
|  
| 7483
|  
|  
|  
|  
Line 333: Line 373:
|  
|  
|-
|-
| go.obo
| [http://oboedit.org/reasoner-benchmarks/go.obo go]
|
| 10.507
| 10.507
| 187.491808
| 187.491808
| 51.812351
| 51.812351
| 40.883224
| 40.883224
| 25.03078
| 23.630003
|  
| 1364
|  
|  
| 1643.285332
| 1643.285332
Line 347: Line 388:
| 27.42
| 27.42
|-
|-
| go_xp_i.obo
| [http://oboedit.org/reasoner-benchmarks/go_xp_i.obo go_xp_i]
|
| 101.995
| 101.995
|  
|  
|  
|  
| 1205.722121
| 1205.722121
| 1384.34991
| 408.745009
| 2395
| 2395
|  
|  
Line 359: Line 401:
|  
|  
| 1117
| 1117
| 607.24
|-
| [http://oboedit.org/reasoner-benchmarks/go_xp_r.obo go_xp_r]
|  
|  
|-
| go_xp_r.obo
| 56.467
| 56.467
|  
|  
|  
|  
| 1020.276001
| 1020.276001
| 706.097357
| 43.711079
|  
| 1427
|  
|  
|  
|  
Line 375: Line 418:
| 388.68
| 388.68
|-
|-
| hp_xp.obo
| [http://oboedit.org/reasoner-benchmarks/hp_xp.obo hp_xp]
|
| 47.689
| 47.689
|  
|  
|  
|  
| 986.551557
| 986.551557
|
| 10736
|
|
|
|
|
|
|-
| [http://oboedit.org/reasoner-benchmarks/mp_xp.obo mp_xp]
|
|
|
|
|
|  
|  
|  
|  
Line 389: Line 448:
|  
|  
|-
|-
| mp_xp.obo
| [http://oboedit.org/reasoner-benchmarks/mp_xp_ch.obo mp_xp_ch]
|  
|  
|  
|  
Line 395: Line 454:
|  
|  
|  
|  
| 2687.581091
|  
|  
|  
|  
Line 403: Line 463:
|  
|  
|-
|-
| nbirn.obo
| [http://oboedit.org/reasoner-benchmarks/mp_xp_cl.obo mp_xp_cl]
|
|
|
|
|
| 10.166375
|
|
|
|
| 222
|
| 20.3
|-
| [http://oboedit.org/reasoner-benchmarks/mp_xp_go.obo mp_xp_go]
|
|
|
|
|
| 78.470274
|
|
|
|
| 92
|
| 57.52
|-
| [http://oboedit.org/reasoner-benchmarks/mp_xp_ma.obo mp_xp_ma]
|
|
|
|
|
|
|
|
|
|
|
|
|
|-
| [http://oboedit.org/reasoner-benchmarks/nbirn.obo nbirn]
| 0.003
| 10.917
| 10.917
|  
|  
|  
|  
|  
|  
|  
| 27.418409
| 984
| 984
|  
|  
Line 417: Line 523:
| 109.04
| 109.04
|-
|-
| nif.obo
| [http://oboedit.org/reasoner-benchmarks/ncithesaurus.obo ncithesaurus]
| 2118.256
| 91.178
| 632.050947
| 58.714178
|
| 122.090551
| 55000
|
| 66.600443
| 745.562156
| 255
| 1592
|
|-
| [http://oboedit.org/reasoner-benchmarks/nif.obo nif]
| 0.004
| 7.274
| 7.274
|  
|  
|  
|  
|  
|  
|  
| 21.840244
| 925
| 925
|  
|  
Line 431: Line 553:
| 58.33
| 58.33
|-
|-
| sao.obo
| [http://oboedit.org/reasoner-benchmarks/obi.obo obi]
| 1.998
| 6.435
|
| 0.90253
|
| 3.379759
| 91
|
| 0.756836
|
| 7
| 28
| 1.04
|-
| [http://oboedit.org/reasoner-benchmarks/sao.obo sao]
|
| 0.17
| 0.17
| 3.125008
| 3.125008
| 0.127607
| 0.127607
| 0.257155
| 0.257155
| 0.166285
| 0.171273
| 20
| 20
|  
|  
Line 445: Line 583:
| 0.52
| 0.52
|-
|-
| so-xp.obo
| [http://oboedit.org/reasoner-benchmarks/so-xp.obo so-xp]
| 0.397
| 0.351
| 0.351
| 6.547285
| 6.547285
| 0.320349
| 0.320349
| 1.423436
| 1.423436
| 0.927108
| 0.959837
| 47
| 47
| 3914.710214
| 3914.710214
Line 459: Line 598:
| 0.97
| 0.97
|-
|-
| tax.obo
| [http://oboedit.org/reasoner-benchmarks/tax.obo tax]
| 0.004
|  
|  
|  
|  
Line 473: Line 613:
|  
|  
|-
|-
| uber.obo
| [http://oboedit.org/reasoner-benchmarks/uber.obo uber]
| 0.853
| 0.889
| 0.889
| 11.993522
| 11.993522
| 10.440892
| 10.440892
| 3.818597
| 3.818597
| 2.674329
| 2.199386
| 89
| 89
|  
|  
Line 487: Line 628:
| 2.28
| 2.28
|-
|-
| xenopus_anatomy.obo
| [http://oboedit.org/reasoner-benchmarks/xenopus_anatomy.obo xenopus_anatomy]
| 0.163
| 0.214
| 0.214
| 3.45821
| 3.45821
| 0.125743
| 0.125743
| 1.356273
| 1.356273
| 0.677572
| 0.6789
| 24
| 24
|  
|  
Line 501: Line 643:
| 0.71
| 0.71
|-
|-
| zfs.obo
| [http://oboedit.org/reasoner-benchmarks/zfs.obo zfs]
| 0.609
| 1.012
| 1.012
| 7.729311
| 7.729311
| 0.868834
| 0.868834
| 4.59457
| 4.59457
| 1.945593
| 1.899504
| 81
| 81
|  
|  
Line 520: Line 663:
The [http://obo.cvs.sourceforge.net/viewvc/obo/obo/website/utils/reasoner-benchmarks.pl?view=log reasoner-benchmarks.pl] script was used.
The [http://obo.cvs.sourceforge.net/viewvc/obo/obo/website/utils/reasoner-benchmarks.pl?view=log reasoner-benchmarks.pl] script was used.


The times above represent actual reasoning time as reported by the reasoner itself. It should exclude time for program to load etc.
The times above represent actual reasoning time (in seconds) as reported by the reasoner itself. It should exclude time for program to load etc.
 
4gb OS X, 32 bit java for OE, java -Xmx2048m


Standard oboInOwl conversion was used for obo ontologies when running with owl reasoners. For OWLAPI tests a custom simple runner was written, see: [http://geneontology.svn.sourceforge.net/viewvc/geneontology/OWLTools/src/owltools/OWLReasonerRunner.java?view=log OWLReasonerRunner]
Standard oboInOwl conversion was used for obo ontologies when running with owl reasoners. For OWLAPI tests a custom simple runner was written, see: [http://geneontology.svn.sourceforge.net/viewvc/geneontology/OWLTools/src/owltools/OWLReasonerRunner.java?view=log OWLReasonerRunner]


==Reasoner Benchmarking on Users' Machines==
[[OE2 Benchmarking by Users]]


[[Category:Reasoning]]
[[Category:Reasoning]]

Latest revision as of 09:02, 12 January 2009

PRELIMINARY benchmarks for various reasoners vs various ontologies.

There is an unashamed GO bias here. We are evaluating with an eye to the project growth of GO particularly w.r.t both internal and external. We also care about database queries as well as ontology maintenance.

OBO-Edit Native Reasoners

oboedit_fcr

OBO-Edit:Forward Chaining Reasoner (LPR). Fast, but only uses the following rules:

  • Transitivity
  • Propagation over/under is_a
  • Intersection_of (aka xps)

John wrote this first in OE1, and then abandoned it. Can still be used for so-xp, and is suitable for certain purposes such as finding trivial redundancies by transitivity, but not recommended in general

oboedit_lpr

OBO-Edit:Link Pile Reasoner (LPR). Successor to FCR.

Rules:

BUGS: there are certain edge cases involving sub-relations and transitivity that do not work. This bug was discovered after John left. The code is difficult to maintain so this reasoner will eventually be abandoned in favour of the RBR (Developer notes: this appears to be due to the fact that sub-relations are computed on the fly rather than cached)

oboedit_rbr

OBO-Edit:Rule Based Reasoner (RBR). Successor to LPR.

The internal design of the RBR is highly simplified compared to the LPR. It was written entirely by cjm. Note the profile is the same as for the LPR, however, the LPR bug does not arise due to the design of the RBR.

Note that the RBR is currently slow for incremental reasoning. This is because it checks all links after any links are added or deleted. This can easily be fixed in future versions. When it is, the LPR will probably be retired altogether.

OWL/DL reasoners

OWL Reasoners are superior to OE reasoners in that they can make use of more expressive constructs, such as complementOf (negation) and universal restrictions (all-only links). However, these constructs are not currently permitted in the OBO 1.2 language.

Some OWL reasoners only recently included transitive_over and arbitrary Relation_composition. They do not allow relation intersections.

Note that OWL reasoners will not allow you to ask questions of the form "what is the heart ventricle part_of?". To allow this we perform an extra step of materializing all transitive relation x class pairs (e.g. "heart part"). This leads to worse performance.

The two main open source OWL reasoners are FaCT++ and Pellet.

Note: even though the table below gives the suffix ".obo", each reasoner was executed on an owl file. These were generated by go2owl whenever the native form of the ontology is obo. If the source is owl then blipkit is used for the reverse translations. See obo-conv. NOTE THAT THIS GIVES AN ADVANTAGE TO OBO REASONERS AS SOME AXIOMS WILL BE DROPPED.

owlapi_pellet

Pellet executed via the OWLAPI (1.2)

owlapi_pellet_mr

As above, with all class x relation pairs materialized.

owlapi_factpp

FaCT++ executed via the OWLAPI (1.2)

owlapi_factpp_mr

As above, with all class x relation pairs materialized.

pellet

Pellet 2.0 executed directly

hermit

Hermit 0.9.2 executed directly.

Note that hermit does not support object property chains -i.e. transitive_over or arbitrary Relation_composition. It will fail on any ontology that includes these. This means a lot of entries are blank.

oboedit_pwr

OBO-Edit pellet-wrapped reasoner. Pellet, executed with OE using a java object level bridge. Performs the class x relation materialization.

Needs updated to the latest Pellet API. May be discontinued in favour of an OWLAPI bridge

Database Reasoners

These reasoners use essentially the same procedure as the oboedit RBR. However, inferred links are backed by a relational database rather than in-memory. As such they tend to be slower, but are not-memory bound. These are also a good choice when the inferred graph needs to be stored in a database, to allow for advanced queries on annotations.

obdsql

Runs off of the OBD SQL schema. See OBD

Uses: Postgres 8.3

  • Transitivity
  • Propagation over/under is_a
  • Subrelations
  • Intersection_of

godb

This is used when loading ontologies into the GO Database. See Transitive_closure

Uses: MySQL 5

Relatively limited set of rules:

Will be extended in future

blipkit

Backed by a prolog database. This is the same reasoner used in obol.See blipkit home page

Results

Availability

See reasoner-benchmarks for the raw data.

Ontologies Used

TODO: show expressivity of each

The following ontologies were used:

Preliminary Benchmarks

THESE RESULTS ARE PRELIMINARY

Blank = program did not complete in allotted time (1-2hrs, varies) OR ran out of memory/heap OR possibly for other reasons, including bugs in my code. At this time, these results should be taken with a pinch of salt.

Also make sure you understand everything above before interpreting. OBO reasoners may have some unfair advantages here.

ONT hermit oboedit_fcr owlapi_pellet_mr owlapi_factpp oboedit_lpr oboedit_rbr obdsql oboedit_pwr owlapi_factpp_mr owlapi_pellet pellet godbsql blipkit
DC_CL 0.154 0.096 3.26185 0.321088 0.269457 0.101434 21 0.344787 3.406521 0 2 0.04
bp_xp_cc 13.476 113.021307 46.33769 1668 1540 80.96
bp_xp_cl 13.589 84.450377 49.550078 1774 1612 89.41
bp_xp_u 14.096 102.442893 52.879202 2043 1545 86.89
caro 0.038 0.018 0.234596 0.013313 0.031378 0.027466 0 1.449529 0.035096 0.159686 0 0 0.01
cc_xp_i 13.36 65.882047 289.564573 1573 1407 67.05
cc_xp_p 0.92 161.977906 19.044575 1.914166 148 1 68 3.59
cell 0.212 0.391 3.015834 0.17246 2.024176 1.039019 32 45.124648 7.315394 2.951417 0 47 1.14
chebt 9.156 105.981208 125.216634 180.321342 2881 100.201565 10 4927
fly 2.847 4.122 43.970665 1.678357 23.575053 10.96353 330 685.638543 42.515054 30 687 18.81
fly_xp 5.514 10.223 5.514895 0.393729 31.695978 22.514039 526 0.390108 5.480391 0 370 24.02
fma2 11.857 33.16 156.072801 10.881829 157.908895 7483 132.435731 61
go 10.507 187.491808 51.812351 40.883224 23.630003 1364 1643.285332 134.506767 9 1143 27.42
go_xp_i 101.995 1205.722121 408.745009 2395 1117 607.24
go_xp_r 56.467 1020.276001 43.711079 1427 32 388.68
hp_xp 47.689 986.551557 10736
mp_xp
mp_xp_ch 2687.581091
mp_xp_cl 10.166375 222 20.3
mp_xp_go 78.470274 92 57.52
mp_xp_ma
nbirn 0.003 10.917 27.418409 984 0 315 109.04
ncithesaurus 2118.256 91.178 632.050947 58.714178 122.090551 55000 66.600443 745.562156 255 1592
nif 0.004 7.274 21.840244 925 0 287 58.33
obi 1.998 6.435 0.90253 3.379759 91 0.756836 7 28 1.04
sao 0.17 3.125008 0.127607 0.257155 0.171273 20 3.157377 3.214984 1 6 0.52
so-xp 0.397 0.351 6.547285 0.320349 1.423436 0.959837 47 3914.710214 57.310919 5.856606 3 25 0.97
tax 0.004 0
uber 0.853 0.889 11.993522 10.440892 3.818597 2.199386 89 3674.025166 11.939288 0 51 2.28
xenopus_anatomy 0.163 0.214 3.45821 0.125743 1.356273 0.6789 24 45.437443 3.069618 0 13 0.71
zfs 0.609 1.012 7.729311 0.868834 4.59457 1.899504 81 442.176979 8.255652 1 98 3.28

Methods

The reasoner-benchmarks.pl script was used.

The times above represent actual reasoning time (in seconds) as reported by the reasoner itself. It should exclude time for program to load etc.

4gb OS X, 32 bit java for OE, java -Xmx2048m

Standard oboInOwl conversion was used for obo ontologies when running with owl reasoners. For OWLAPI tests a custom simple runner was written, see: OWLReasonerRunner

Reasoner Benchmarking on Users' Machines

OE2 Benchmarking by Users