Results comparing RC_Link 2.0 and Superlink 1.5

November 3, 2005

Experimental Methods

The following results were performed using RC_Link version 2.0 and Superlink version 1.5 (the newest releases of both). The experiments were run on an Intel Xeon 2.4 GHz processor on a machine with 4GB of RAM (however the currently installed Java virtual machine only allowed RC_Link to access 2GB of it, however since Superlink is not a Java program it does not have this limitation).

The networks chosen include a subset of those provided with previous versions of Superlink (including all those which required more than 3 seconds for Superlink to do its computations on) and all of the challenging networks provided with the most recent versions.

As both programs use non-deterministic algorithms, their run time may vary significantly from one run to the next. We therefore ran each tool 5 times on each network and provide an average over those runs.

Experimental Results

It can be seen from the first two datasets (EA and EB) that these networks are no longer too challenging for either tool, as both can solve them fairly quickly {It should be noted that just a few years ago in 2003 many of these networks were very challenging and some of them were not even able to be solved in a reasonable amount of time.} We really start to see the differences between the two programs when we analyze the newer, more challenging networks in the third dataset. It can be seen that RC_Link is faster than Superlink on all these networks except for number 50, and on many of them the difference is orders of magnitude. For example we were able to do network 18 in just 5 seconds compared with 11795, network 7 in 23 seconds compared with 165, network 25 in 27 seconds compared with 2,059, and network 33 in just 4 seconds compared with 350. Even on networks 44 and 51, which Superlink required 2490 seconds and 2369 seconds on, we were able to do significantly faster at just 121 seconds and 557 seconds respectively.

Table 1: Experimental Results (in Seconds)

Network	Number People	Number Loci	Superlink	RC_Link
EA7	57	14	1.0	3.9
EA8	57	18	4.0	4.3
EA9	57	37	8.9	6.4
EA10	57	38	15.0	6.7
EA11	57	43	16.5	7.2
EB3	100	12	9.8	4.9
EB4	100	13	4.1	5.1
EB5	100	14	5.0	5.4
EB6	100	15	9.3	5.6
EB7	100	16	10.9	5.8
EB8	100	17	9.4	6.2
EB9	100	18	9.4	6.3
EB10	100	19	9.4	6.5
EB11	100	20	12.7	6.7
1	25	7	78.7	24.5
7	25	20	164.6	22.9
9	20	20	184.5	168.6
13	20	20	234.0	98.7
18	20	20	11794.8	5.4
19	15	20	107.2	19.2
20	25	7	172.3	34.1
23	25	7	216.1	3.2
25	25	20	2058.9	26.7
30	25	20	2716.3	5.9
31	25	20	2064.2	144.9
33	25	20	349.6	3.9
34	25	20	962.8	31.7
37	57	6	1004.8	66.2
38	57	4	---	425.4
39	25	20	424.5	9.9
40	20	20	917.2	57.6
41	25	20	665.9	13.4
42	25	7	1799.1	36.2
44	20	20	2489.9	121.4
50	57	4	9712.2	26411.6
51	25	20	2368.6	556.5

Copyright 2005. All Rights Reserved.