Algorithm Companion Cocitation Netscape
Companion 253 (51%) 55 (11%)
Cocitation 253 (44%)
Netscape 55 (15%) 56 (15%)
Table 7: Overlap between answers returned by algorithms
Companion time (msec)
Cocitation time (msec)
0 5000 10000 15000
0 2000 4000 6000
# of siblings
Figure 2: Graph size vs. running time of Companion and Cocitation algs.
given URL if they did not return any answers. This mostly a ected the Netscape and Companion
algorithms. The second reason is that for the URLs in the non-Netscape set, both the Companion
and Cocitation algorithms did not perform as well as they did for URLs in the Intersection set.
Despite these drops in absolute average precision, the average precision of the Companion algorithm
is 57% better than that of Netscape, and the average precision of the Cocitation algorithm is 51%
better than that of Netscape. Similar results hold when examining average precision rather than
precision at 10.
To evaluate the statistical signi cance of our results, we computed the Sign Test and the Wilcox-son Sums of Ranks Test for each pair of algorithms . These results are shown in Table 6 and show
that the di erence between the Companion and Netscape algorithms and between the Cocitation
and Netscape algorithms are statistically signi cant.
We also wanted to evaluate whether or not the algorithms were generally returning the same
results for a given URL or whether they were returning largely disjoint sets of URLs. Table 7
shows the amount of overlap in the answers returned by each pair of algorithms. The percentage in
parentheses is the overlap divided by the total number of answers returned by the algorithm in that
row. As the table shows, there is a large overlap between the answers returned by the Companion
and Cocitation algorithms. This is not surprising, since the two algorithms are both based on
connectivity information surrounding the input URL and since both use similar parameters to
choose the surrounding nodes. There is relatively little overlap between the answers returned by
Netscape and the other two algorithms.
4.3 Run-time Performance
In this section, we present data about the run-time performance of the Companion and Cocitation
algorithms. Since we do not have direct access to Netscape's algorithm and only access it through
the public web interface, we are unable to present performance information for Netscape's algorithm.