times. In a way, this problem is reminiscent of the com- putation of spatial joins on objects embedded in the Eu- clidean space: the spatial datasets are delivered online and we need to compute the best spatial matches [16]. Only that, in the case of ontologies, the primitive distance is not Euclidean, but computed on a tree. The problem we consider here can be extended easily to the case when objects are annotated with multiple in- dependent ontologies. We can compute the per-ontology distance and combine them using an aggregate ranking technique such as the threshold algorithm [7]. The prob- lem of finding objects similar to a given query object (i.e., the k -NN problem) reduces to the special case of a join of the database with a singleton set, the query object. Simi- larly, range queries can be solved by choosing only those pairs having a distance less than the query range. While these and other kinds of queries can also be considered in our setting, the problem of top- k joins exposes the compu- tational and data management complexities of this domain well, making it the right problem to consider. Formally, our problem can be stated as: Problem 1. Given a set of objects each of which is defined by a set of terms from an ontology and a distance function d ( O$_{i}$, O$_{j}$ ) between two objects O$_{i}$ and O$_{j}$ , find k pairs of objects P such that for any ( O$_{i}$, O$_{j}$ ) ∈ P and ( O$_{g}$, O$_{h}$ ) / ∈ P , d ( O$_{i}$, O$_{j}$ ) ≤ d ( O$_{g}$, O$_{h}$ ) . Figure 1 illustrates a particular instance of the problem. The ontology tree consists of 10 terms. There are 4 objects that are described by these terms. The object descrip- tions are given by O 1 = { t 1 , t 7 } , O 2 = { t 0 , t 1 , t 4 , t 5 } , O 3 = { t 2 , t 3 , t 9 } , O 4 = t 6 , t 8 } . An inverted index, i.e., mapping a term to set of objects can be maintained on the ontology itself (as shown in the figure). Thus, each node in the tree statically maintains a list L of the objects that are described using the term corresponding to the node. For example, the list of objects for t 0 is ( O $_{2}$). We will use term and node interchangeably to denote the node in which the term resides. The edge weights on the tree decrease exponentially as the level increases. Concepts closer to the root of the ontology are less similar than concepts that share some common ancestors. For example, broader concepts such as “sports” and “politics” should be more dissimi- lar than relatively narrower concepts such as “football” and “cricket”. The exponentially decreasing edge weights capture this notion. We highlight the fact that the expo- nential edge weighting function is an example, and not a necessity for the algorithms to work. They produce cor- rect answers for all edge weights. We denote the number of objects by N , the number of terms by T , the total information size (i.e., the total number of describing terms for all the objects) by D , and the number of object pairs queried by k . In Figure 1, N = 4 , T = 10 , and D = 11 . Our contributions in this paper are as follows: The rest of the paper is organized as follows. Section 2 describes the related work. Section 3 defines the term 1. First, we propose the problem of finding top- k most similar object pairs that are annotated with terms in a hierarchy in an online fashion. The terms may de- fine concepts in an ontology and objects may be de- scribed using the concepts. 2. Then, we define and motivate three different distance functions (equivalently, similarity measures) that can be used to describe the similarity between a pair of objects. The minimum pairwise distance is useful for searching objects sharing a similar term (con- cept). The average pairwise distance can be used to query objects that are described using multiple at- tributes. The earth mover’s distance (EMD) finds the best way of matching the terms from two objects and finds the distance corresponding to this best match- ing. 3. Finally, we develop efficient algorithms to solve the problem using the above distances. We use lower bounds based on L 1 on reduced number of terms to speed up the computation of EMD. The L 1 distance, in turn, is computed progressively using a modified version of the threshold algorithm. For the minimum pairwise distance, we show that the top- k query runs in O ( Tk log k ) time, where T is the size of the ontol- ogy. For the average pairwise distance, we devise an efficient best-first search algorithm that avoids dis- tance computations by generating lower bounds in an ordered manner. Experimental evaluations demon- strate the scalability and practicality of our algo- rithms. 2 Figure 1: Example of an ontology tree with objects. o$_{1}$:t $_{1}$,t 7 o$_{2}$:t $_{0}$,t $_{1}$,t $_{4}$,t 5 o$_{3}$:t $_{2}$,t $_{3}$,t 9 t$_{1}$ t$_{2}$ t$_{3}$ t$_{4}$ t$_{5}$ t$_{6}$ t$_{7}$ t$_{8}$ t$_{9}$ t$_{0}$ o$_{4}$:t 6 8 ,t o$_{2}$ o$_{1}$,o$_{2}$ 3 o o$_{3}$ o$_{2}$ o$_{2}$ o$_{4}$ o$_{1}$ o$_{4}$ o$_{3}$ 1 1 1 0.5 0.5 0.5 0.5 0.5 0.5