Figure 13: Effect of k on AvgDist. Figure 11: Effect of k on MinDist. Figure 12: Effect of T on MinDist. 7.10 Effect of N on MinDist 7.11 Effect of k on AvgDist 7.8 Effect of k on MinDist 7.9 Effect of T on MinDist 7.12 Number of Object Pairs for AvgDist  0  0.2  0.4  0.6  0.8  1  1.2  1.4 0  10  20  30  40  50  60  70  80  90 100 Running time (s) k MinDist: Gene Ontology (GO) datasets GO Process GO Function GO Localization  0  5  10  15  20  25  0  10  20  30  40  50  60  70  80  90  100 Running time (s) k AvgDist: Gene Ontology (GO) datasets GO Process: Build GO Process: NextEstimate GO Process: Complete GO Function: Build GO Function: NextEstimate GO Function: Complete  0  20  40  60  80  100  2  2.5  3  3.5  4  4.5  5  5.5 6 Running time (s) log$_{10}$ T MinDist: Synthetic dataset, N=10 6 k=1 k=5 k=10 k=25 k=50 k=100 The first set of experiments measure the effect of th e num- ber of top pairs queried ( k ), on the running time of the MinDist algorithm. As shown in Figure 11, the scala- bility of MinDist with k is linear. The analysis d one in Section 5.1 shows that for small values of k , this is the ex- pected behavior. The largest real dataset—GO proc ess— finishes in less than 1 s for k ≤ 50 , demonstrating the effectiveness of the algorithm. We next report the effect of the number of terms T on the running time. Figure 12 shows that increasing T in- crements the running time of MinDist linearly, indepen- dent of the value of k . We also note the practicality of the MinDist algorithm. For a very large dataset of size N = 10 6 and a very large tree of size T = 10 $^{6}$, a top- 100 query finishes in about 100 s. For smaller k ’s and for smaller T ’s, the running time is in seconds. The running time analysis of the MinDist algorithm shows that it is independent of the number of objects N . When the number of terms T is kept constant, the experiments confirm that the running time is practically constant even when N is increased from 10 3 to 10 6 (graph not shown). The next set of experiments evaluate the performance of the two variants of AvgDist. The first experiment on AvgDist illustrates the effect of k on the running time of the Build phase and the two differ- ent variants—NextEstimate and Complete—for the two larger GO datasets. All the six curves in Figure 13 are rel- atively flat, showing that the effect of k is minimal. Intu- itively, the running time of AvgDist depends on the actual number of object pairs investigated. For the GO datasets, even for even large k ’s up to 100 , this remains almost con- stant. Moreover, the Build phase takes negligible time in comparison to the Query phase. We further investigated the effect of k by measuring the number of object pairs that are examined in the Query phase of the AvgDist algorithm. For this, we increased k up to 10000 . Figure 14 shows that η (i.e., the ratio to the total number of possible pairs) increases very slowly with k . The results are robust across different values of T (as shown in the figure) and N (not shown). This is the reason why the running time is also constant across k . The NextEstimate method examines less than 2% of the total number of pairs. The Complete method inves- tigates more object pairs (about 7%) than the NextEsti- mate method. Computing a distance for the current best- pair guarantees that only those pairs which have a bound 14