7 Experiments 7.1 Datasets 7.2 Experimental Setup 7.3 Effect of k on EMD 12 $^{10}$Figure 17 in Appendix outlines the algorithm. We have experimented with real as well as synthetic datasets. The real dataset is that of Gene Ontology (GO, http://www.geneontology.org/). There are three ontolo- gies in GO, corresponding to biological process, molec- ular function and cellular component (localization) of terms. The details of the three ontologies are given in Ta- ble 5. The datasets were curated by hashing gene descrip- tions using their bit-vector representations of the terms and removing the identical genes. The synthetic datasets were generated by controlling the number of objects, the number of terms, the aver- age branching factor of the ontology tree and the average number of terms per object. The ontologies and the object datasets are created separately. Ontologies have a fixed size and an average branching factor. Starting from the root, we generate a random number of children by per- turbing the average branching factor within some limits. We continue with this at all successive nodes. The object dataset is generated with a fixed number of objects and an average number of terms per object. Again, a random number is generated from the average by perturbing it. Then, terms are picked from the ontology randomly with- out replacement for the required number of terms. This process is repeated for all objects. When the distance function between the objects is defined as the earth mover’s distance the following schemes were evaluated: The performance of the brute-force scheme (267 s for N = 100 objects) is too impractical to be of any use and are, therefore, not reported. Also, the times of L $_{1}$-full are Figure 7 shows the effect of k on the running time of GO localization dataset. When k is increased, more number of L 1 computations are needed before the TA can halt. Consequently, more number of EMD calculations are also required. The performance of the brute-force scheme (300 s for 10 4 dataset) is much higher than that for AvgDist schemes. Consequently, it is not discussed any further. Sections 7.3 to 7.7 report experiments on EMD while Sections 7.8 to 7.10 and 7.11 to 7.14 report on MinDist and AvgDist respectively. For N = 10 $^{4}$, the top- k computation using the brute-force algorithm finishes in ∼ 300 s. Since the MinDist has a bet- ter running time, we report the experiments for MinDist only. When the distance function between the objects is de- fined as the average pairwise distance between the terms, the following schemes were evaluated: not reported since, in the best case, it can only save L $_{1}$- reduced computations, which are very fast anyway. In all the experiments, it was actually worse than L $_{1}$-reduced. When the distance function between the objects is defined as the minimum pairwise distance between the terms, the following schemes were considered: • L $_{1}$-reduced: In this scheme (Section 4), the L 1 on reduced number of terms is used. • L $_{1}$-full: In this scheme, the L 1 on all terms is used. The tree is not pruned at a height 1 . • EMD-reduced: All the O ( N $^{2}$) EMDs on reduced number of terms are computed. These are then used to prune those object pairs for which the reduced EMD is greater than the k th best EMD already found. • Brute-force: In this scheme, all the O ( N $^{2}$) pairs are computed and then the top- k pairs are returned. • AvgDist-NextEstimate: In this variant of AvgDist, the estimate for the best-pair is improved by progres- sively descending into the subtrees and estimating the across-tree costs at the roots of those subtrees. • AvgDist-Complete: This is the other variant of AvgDist where the exact distance is computed at one go by computing all the pairwise term distances. • Brute-force: In this scheme, all the O ( N $^{2}$) pairs are computed and then the top- k pairs are returned. • MinDist: This is the scheme described in Section 5 that has a running time of O ( Tk log k ) . • Brute-force: In this scheme, all the O ( N $^{2}$) pairs are computed and then the top- k pairs are returned. Maintaining a heap of size at most k gives the run- ning time of this scheme to be O ( N 2 log k ) . Due to the exorbitant online costs of it, this scheme is not practically useful.