1 Finding Top-k Similar Pairs of Objects Annotated with Terms from an Ontology Arnab Bhattacharya Abhishek Bhowmick Ambuj K. Singh ambuj@cs.ucsb.edu bhowmick@iitk.ac.in arnabb@iitk.ac.in Dept. of Computer Science and Engineering, Indian Institute of Technology, Kanpur Kanpur, UP 208016, India. Dept. of Computer Science and Engineering, Indian Institute of Technology, Kanpur Kanpur, UP 208016, India. Dept. of Computer Science, University of California, Santa Barbara Santa Barbara, CA 93106, USA. tics. Annotated objects occur in multiple application do- mains including language (http://wordnet.princeton.edu/), biology (http://www.geneontology.org), medical doc- uments (http://www.nlm.nih.gov/mesh/), web content (http://www.semanticweb.org/), etc. In all these cases, an- notations are derived from a structured vocabulary or on- tology. An ontology uses a number of different relation- ships (e.g., is-a, is-part-of) to organize concepts or hierar- chies. This paper investigates the analysis of large sets of ob- jects that have been annotated with terms from a common ontology. The basic problem we consider is as follows: Given two sets of objects annotated with terms from a common ontology, how to find the top- k pairs of objects among the two sets that are most similar. The above problem statement requires us to formalize the notion of distance between two terms in a given ontol- ogy and then to extend this notion to distance between two annotated objects . The distance between two terms can be measured by the shortest path distance on the ontology. There are a number of definitions for distance (or con- versely, similarity) between objects. Two obvious defini- tions are based on the minimum pairwise distance and the average pairwise distance between the annotations. The third one is the earth mover’s distance [12] that takes into account the relative positions of the terms that describes the objects. We investigate querying based on these three distance measures. In this paper, we consider that the object descriptions are submitted in an online fashion, i.e., they are available only at run-time. As such, no pre-processing or index con- struction or any other offline processing can be used, and all the computation costs are paid at run-time. Even if the distance function used is a metric, the online nature of the problem renders the use of index structures like the M-tree [3] infeasible due to their high index construction We are witnessing an unprecedented growth in annotated information. This growth has been motivated by a need to share information and, more recently, by a need to search and analyze objects based on their structure and seman- With the growing focus on semantic searches and inter- pretations, an increasing number of standardized vocabu- laries and ontologies are being designed and used to de- scribe data. We investigate the querying of objects de- scribed by a tree-structured ontology. Specifically, we consider the case of finding the top- k best pairs of ob- jects that have been annotated with terms from such an ontology when the object descriptions are available only at runtime. We consider three distance measures. The first one defines the object distance as the minimum pair- wise distance between the sets of terms describing them, and the second one defines the distance as the average pairwise term distance. The third and most useful dis- tance measure—earth mover’s distance—finds the best way of matching the terms and computes the distance corresponding to this best matching. We develop lower bounds that can be aggregated progressively and utilize them to speed up the search for top- k object pairs when the earth mover’s distance is used. For the minimum pairwise distance, we devise an algorithm that runs in O ( D + Tk log k ) time, where D is the total information size and T is the total number of terms in the ontology. We also develop a novel best-first search strategy for the aver- age pairwise distance that utilizes lower bounds generated in an ordered manner. Experiments on real and synthetic datasets demonstrate the practicality and scalability of our algorithms. Abstract 1 Introduction arXiv:1001.2625v2 [cs.DB] 6 Mar 2010