6 The Algorithm for AvgDist 6.1 Lower Bounds for Across-Tree Costs amortized cost is O ( Tk + Tk log k ) = O ( Tk log k ) . The total running time of the MinDist algorithm is, therefore, O ( D + Tk log k ) . Space Complexity: Each node in the ontology contains an object list of size O ( k $^{′}$) and a pair list of size O ( k ) . Once these lists are sent to the parent, they are no longer required. Thus, at any time, the space requirement at a node is O ( c ( k ′ + k )) . The total space complexity, there- fore, is O ( c$_{max}$ ( k + k $^{′}$)) where c$_{max}$ is the largest branch- ing factor of a node in the tree. The inverted index requires O ( D ) space for storage. Unlike the MinDist algorithm that needs to maintain only one term pair for each object pair, the d$_{avg}$ distance needs to remember all the possible term-pair distances. Conse- quently, it runs in two phases: (i) the Build phase, when pertinent information about objects are collected at the root in a bottom-up manner, and (ii) the Query phase, when such information is used to identify the top- k pairs in a top-down order. For any pair of objects, there are two types of costs that need to be accumulated. The first is the across-tree costs, i.e., the distances between the describing terms that oc- cur in different subtrees of the root, and the second is the within-tree costs, i.e., the distances between the describ- ing terms that are within the same child of the root. For example, in Figure 1, the total pairwise term distances for ( O 1 , O $_{4}$) can be broken into 2 parts: (i) the across-tree distances between t 1 of O 1 and t $_{6}$, t 8 of O 4 in the dif- ferent subtrees under t 1 and t 2 respectively, and (ii) the within-tree distances between t 7 of O 1 and t $_{6}$, t 8 of O 4 in the same subtree under t $_{2}$. To estimate the across-tree distances for object pairs at a node, the following information need to be calculated for each object: (i) the number of terms in the subtree that describe the object, and (ii) the total distance of all such terms to this node. This information is accumulated at the root of the ontology by the build phase AvgDist- Build, which we describe in Section 6.4. After this phase, the root has collected the following tuple for each object: ( O$_{i}$ , n$_{i}$ , w$_{i}$ ). Before describing the two phases of the algorithm, we explain how lower bounds for the across-tree costs of an object pair can be computed using the above information and how such lower bounds can be generated in an or- dered manner. The estimates of the across-tree distances of a pair of objects O$_{i}$ and O$_{j}$ at a node t depend on the occurrences of their describing terms. The span of an object is defined to be the number of subtrees of the root where its constituent terms occur. It can be either single, i.e., its terms occur in only one subtree, or multiple, i.e., its terms occur in multiple subtrees. Based on these, 3 different cases need to be considered. In each case, we would like to write the bounds at a node in terms of the parameters maintained for O$_{i}$ and O$_{j}$ at the node, i.e., in terms of ( O$_{i}$ , n$_{i}$ , w$_{i}$ ) and ( O$_{j}$ , n$_{j}$ , w$_{j}$ ). Case 1: Both the objects have single spans. Two sub- cases need to be considered. Sub-case 1(a): The objects are in the same subtree. The across-tree cost is 0 and nothing can be concluded about their distance in the subtree without descending deeper into the subtree. Hence, the lower bound is Sub-case 1(b): The objects are in different subtrees. In this case, the across-tree distance can be estimated ex- actly. The distance between a term t$_{i}$ ∈ O$_{i}$ and t$_{j}$ ∈ O$_{j}$ is d ( t$_{i}$, t ) + d ( t$_{j}$, t ) where t is the node at which this lower bound is being computed. The total across-tree distance is obtained by adding all such combinations of terms: Thus, the average distance is Since the within-tree distance for this pair is 0 , this is the exact distance. Case 2: Both the objects have multiple spans. The min- imum across-tree distance can be estimated in a manner similar to that in Case 1(b). There are at least two pair- ings of terms of O$_{i}$ and O$_{j}$ that are in different subtrees. Using Eq. (5), the total across-tree costs for these pairings are w$_{i}$$_{1}$.n$_{j}$$_{2}$ + w$_{j}$$_{2}$.n$_{i}$$_{1}$ and w$_{i}$$_{2}$.n$_{j}$$_{1}$ + w$_{j}$$_{1}$.n$_{i}$$_{2}$ , where n$_{i}$$_{1}$ , w$_{i}$$_{1}$ etc. are the number of terms of O$_{i}$ in one subtree and 9 d$_{lb}$ = 0 (4) | O$_{j}$ | ∑ j =1 | O$_{i}$ | ∑ i =1 d ( t$_{i}$, t ) +$^{|}$$^{O$_{i}$}$$^{|}$ ∑ i =1 | O$_{j}$ | ∑ j =1 d ( t$_{j}$, t ) = n$_{j}$.$^{|}$$^{O$_{i}$}$$^{|}$ ∑ i =1 d ( t$_{i}$, t ) + n$_{i}$.$^{|}$$^{O$_{i}$}$$^{|}$ ∑ i =1 d ( t$_{j}$, t ) = n$_{j}$.w$_{i}$ + n$_{i}$.w$_{j}$ (5) d$_{lb}$ = d = w$_{i}$ n$_{i}$ + w$_{j}$ n$_{j}$ (6)