its total distance to t from that subtree. The values of n$_{i}$$_{1}$ , n$_{i}$$_{2}$ , n$_{j}$$_{1}$ , and n$_{j}$$_{2}$ are at least 1 . Thus, the total across-tree distance is at least w$_{i}$$_{1}$ + w$_{i}$$_{2}$ + w$_{j}$$_{1}$ + w$_{j}$$_{2}$ = w$_{i}$ + w$_{j}$ . The lower bound for the average pairwise distance, then, is Case 3: One object O$_{i}$ has a single span, and the other object O$_{j}$ has a multiple span. Similar to Case 2, there is at least one subtree containing terms of O$_{j}$ but not con- taining terms of O$_{i}$ . The total across-tree cost is then the minimum of w$_{i}$.n$_{j}$$_{1}$ + w$_{j}$$_{1}$.n$_{i}$ and w$_{i}$.n$_{j}$$_{2}$ + w$_{j}$$_{2}$.n$_{i}$ . Sim- ilar to Case 2, there is at least one term of O$_{j}$ that is not in the same subtree of O$_{i}$ . Thus, n$_{j}$$_{1}$ and n$_{j}$$_{2}$ are at least 1 . However, without knowing where the terms of O$_{j}$ oc- cur, nothing can be concluded about w$_{j}$$_{1}$ and w$_{j}$$_{2}$ . Since the terms may occur at the node itself, the estimates for w$_{j}$$_{1}$ and w$_{j}$$_{2}$ are 0 . Hence, the total distance is at least w$_{i}$ producing a lower bound of Though the above mentioned lower bounds can be com- puted for a given pair, the cost of computing them for ev- ery pair is O ( N $^{2}$) . We would like to avoid such costly online operations. The trick is to separate the parameters of O$_{i}$ and O$_{j}$ in each lower bound such that they can be systematically generated in an ordered manner whenever needed. The order of generation will guarantee that at any point of time, the lower bounds of the pairs not exam- ined will be greater than or equal to the lower bounds of the pairs already generated. In this section, we will dis- cuss ways to achieve this for each of the cases mentioned above. To identify pairs of objects in the same subtree (Case 1(a)), c +1 different lists are maintained at the root corre- sponding to itself and its c children. To handle Case 1(b), each of these c +1 lists of objects are sorted by the average distance w$_{i}$/n$_{i}$ . Given two such sorted child lists, it is guaranteed that the lower bound (which is the sum of the distances) for an object pair at positions p$_{i}$ in the first list and p$_{j}$ in the second list is lower than the estimate of every pair whose positions are > p$_{i}$ and > p$_{j}$ . Thus, every time a pair at positions ( p$_{i}$,p$_{j}$ ) is inspected, only its immediate successors ( p$_{i}$ + 1 ,p$_{j}$ ) and ( p$_{i}$,p$_{j}$ + 1) need to be considered. Since there are c +1 child lists, the number of possible ways of pairing is c ( c + 1) / 2 . The lower bound for Case 2 is not easily separable in terms of parameters of O$_{i}$ and O$_{j}$ . It is, however, sep- arable if for an object pair, the number of terms for the objects (i.e., n$_{i}$ , n$_{j}$ ) are known a priori. To do that, the list of objects with multiple spans is partitioned such that each partition contains objects with a particular n$_{i}$ . Pair- ing O$_{i}$ and O$_{j}$ and knowing which partitions they come from immediately defines the denominator of the lower bound. Thus, if there are r partitions, sorting each par- tition by w$_{i}$ and performing r 2 pairings in the same way as done for Case 1(b) orders the pairs according to their lower bounds. Case 3 is handled similarly. The single-span list is bro- ken into c + 1 lists and the multiple-span list into r par- titions. Generating all r ( c + 1) pairings gives the lower bounds in an ordered manner. We next describe how the Query phase of the AvgDist algorithm uses these lower bounds. The AvgDist-Query procedure (Figure 6) is run at the root of the ontology. It outputs a list P of top- k object pairs. When the size of P is less than k , P.dist is ∞ ; otherwise, it is maintained as the k th largest distance in P . The list L of objects is broken into c + 1 + r lists cor- responding to single and multiple spans as explained in the earlier section. From these lists, the initial pairs with the lower bounds are generated (method GenInitialPairs in line 6) and put into a heap H . See Section 6.2 for details on how to generate these pairs. The top-down searching for object pairs proceeds in a manner where at every stage, only the current “best” pair is examined [10]. Thus, this search strategy is called the best-first search . The algorithm progresses by extracting the current best pair from the heap, i.e., the pair p with the current best lower bound (line 8). If the lower bound is an estimate for p and not an exact distance as in Case 1(b), the bound can be improved in two ways (line 11). First, the within- tree costs at the subtrees in the next level can be estimated again using Eqs. (4-8) by descending into the subtree (de- noted as AvgDist-NextEstimate). The descent is made in a breadth-first order on the tree. 9 The second way is to compute the term-wise distances fully without resorting to recursion (denoted as AvgDist-Complete). This, how- ever, disregards the structure of the ontology. If the exact distance of p is computed, the list P is ex- amined. If the k th distance in P is more than that of p (line $^{9}$Any order, e.g., depth-first order, will also work. However,if the edge distances decrease exponentially, breadth-first orde ring produces better bounds. 6.2 Generating Ordered Pairs 6.3 Query Phase d$_{lb}$ = w$_{i}$ n$_{i}$.n$_{j}$ (8) d$_{lb}$ = w$_{i}$ + w$_{j}$ n$_{i}$.n$_{j}$ (7) 10