References perimental evaluations demonstrated the practicality and scalability of our algorithms. In future, we would like to design algorithms for other distance measures and lower bounds. We would also like to develop methods that use term statistics to improve the expected running time and further explore the opti- mal height of pruning the ontology tree for EMD. Lastly, algorithms for k -NN and range queries should be simple extensions of the proposed algorithms. Figure 16: Effect of T on Build phase of AvgDist.  0  5  10  15  20  25  2  2.5  3  3.5  4  4.5  5  5.5  6 Build time (s) log$_{10}$ T AvgDist: Synthetic dataset, k=1 N=10 2 N=10 3 N=10 4 [1] I. Assent, A. Wenning, and T. Seidl. Approximation techniques for indexing the earth mover’s distance in multimedia databases. In ICDE , pages 11–22, 2006. [2] M. Brameier and C. Wiuf. Co-clustering and vi- sualization of gene expression data and gene ontol- ogy terms for Saccharomyces cerevisiae using self- organizing maps. J. Biomed. Inf. , 40(2):160–173, 2007. [3] P. Ciaccia, M. Patella, and P. Zezula. M-tree: An ef- ficient access method for similarity search in metric spaces. In VLDB , pages 426–435, 1997. [4] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms . MIT Press, 2001. [5] F. M. Couto, M. J. Silva, and P. M. Coutinho. Mea- suring semantic similarity between gene ontology terms. Data & Knowledge Engg. , 61(1):137–152, 2007. [6] S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent se- mantic analysis. J. Am. Soc. Inf. Sc. , 41(6):391–407, 1990. [7] R. Fagin, A. Lotem, and M. Naor. Optimal aggre- gation algorithms for middleware. In PODS , pages 102–113, 2001. [8] X. Guo, R. Liu, C. D. Shriver, H. Hu, and M. N. Liebman. Assessing semantic similarity measures for the characterization of human regulatory path- ways. Bioinf. , 22(8):967–973, 2006. [9] A. Gupta. Embedding tree metrics into low dimen- sional euclidean spaces. In STOC , pages 694–700, 1999. [10] G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Trans. Database Syst. , 24(2):265–318, 1999. [11] E. Johnston and N. Kushmerick. Web service ag- gregation with string distance ensembles and active probe selection. Information Fusion , 9:481–500, 2008. [12] V. Ljosa, A. Bhattacharya, and A. K. Singh. In- dexing spatially sensitive distance measures using multi-resolution lower bounds. In EDBT , pages 865–883, 2006. [13] P. W. Lord, R. D. Stevens, A. Brass, and C. A. Goble. Investigating semantic similarity measures across the gene ontology: the relationship between sequence and annotation. Bioinf. , 19(10):1275– 1283, 2003. [14] L. Mari˜no-Ram´ırez, O. Bodenreider, N. Kantz, and I. K. Jordan. Co-evolutionary rates of functionally related yeast genes. Evolutionary Bioinf. , 2:271– 276, 2006. [15] R. Mihalcea and C. Corley. Corpus-based and knowledge-based measures of text semantic similar- ity. In AAAI , pages 775–780, 2006. [16] J. M. Patel and D. J. DeWitt. Partition based spatial- merge join. In SIGMOD , pages 259–270, 1996. [17] G. Salton and C. Buckley. Term-weighting ap- proaches in automatic text retrieval. Inf. Proc. & Mgmt. , 24(5):513–523, 1988. [18] Y. Tao, L. Sam, J. Li, C. Friedman, and Y. A. Lussier. Information theory applied to the sparse gene ontol- ogy annotation network to predict novel gene func- tion. Bioinf. , 23(13):i529–i538, 2007. [19] X. Wan and Y. Peng. The earth mover’s distance as a semantic measure for document similarity. In CIKM , pages 301–302, 2005. 16