<- Previous | First | Next ->

Algorithm Companion Cocitation Netscape

Companion 253 (51%) 55 (11%)

Cocitation 253 (44%)

56 (10%)

Netscape 55 (15%) 56 (15%)

Table 7: Overlap between answers returned by algorithms

DeviceRGB 3 bits

Companion time (msec)

Cocitation time (msec)

400

600

DeviceRGB 3 bits
DeviceRGB 3 bits
DeviceRGB 3 bits

300

400

200

DeviceRGB 3 bits
DeviceRGB 3 bits

200

100

0

0

0 5000 10000 15000

0 2000 4000 6000

Graph edges

# of siblings

(a)


(b)



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 [20]. 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.

11


<- Previous | First | Next ->