6.4 Build Phase Figure 6: The Query phase of the AvgDist algorithm. Table 5: The Gene Ontology (GO) datasets. Algorithm AvgDist-Query Input: Node root Output: Pair list P of size k 1. L := list of object mappings in root 2. P := Φ (therefore, P.dist := ∞ ) 3. c := number of children of root 4. r := number of partitions of objects 5. Divide L into c + 1 + r lists B 6. A := GenInitialPairs( B ) 7. Insert each a ∈ A into heap H 8. p := Pop( H ) 9. while p.dist < P.dist 10. if Done( p ) = false 11. p := UpdateEstimate( p ) 12. end if 13. if Done( p ) = true 14. if p.dist < P.dist 15. Insert p into P 16. P.dist := k th distance in P 17. end if 18. else 19. Insert p into H 20. end if 21. A := GenNextPairs( p , L ) 22. Insert each a ∈ A into H 23. p := Pop( H ) 24. end while Name Number of Number of GO Terms ( T ) Genes ( N ) Process 13762 3437 Function 7803 1958 Localization 1990 645 In this section, we describe how AvgDist-Build computes the information ( O$_{i}$ , n$_{i}$ , w$_{i}$ ) for an object. 10 Each node t maintains an inverted list L of objects O$_{i}$ described using t . First, it converts L into B by making n$_{i}$ = 1 and w$_{i}$ = 0 for each O$_{i}$ ∈ L . Then, it calls AvgDist-Build for each of its children. For each list CB that it receives from a child, and for each object O$_{j}$ ∈ CB , it modifies w$_{j}$ by adding to it the distance to the child node multiplied by the number of times O$_{j}$ occurs in the child subtree, i.e., w$_{j}$ = w$_{j}$ + dist × n$_{j}$ , where dist is the edge distance from t to its child. This ensures that the total distance from t is maintained correctly, since each of the n$_{j}$ objects have to traverse the distance dist . 14), p is inserted into P and P.dist is modified. The size of P is maintained to be at most k by removing the pair with the largest distance. If, however, the lower bound of p is still an estimate, p is re-inserted back into the heap H (line 19). The next pairs are generated from the c + 1 + r lists (method Gen- NextPairs in line 21 as described in Section 6.2) and in- serted into the heap (line 22). In the next iteration, the pair which is now the best is examined (line 23). If this pair has a distance more than the k th distance in P (i.e., P.dist ), it is guaranteed that all the pairs currently in the heap and all the pairs that are not generated will have a greater distance. This is due to the properties of the heap and the ordered nature of generating the pairs from the c + 1 + r lists. Thus, the algorithm is then terminated correctly. Analysis of Space and Time Complexities: Assume the total size of the object description to be D which is at most N × T where N is the total number of objects, and T the total number of terms. The inverted index requires O ( D ) time and space to construct. We next analyze the space and time complexity of AvgDist-Build in terms of these parameters. Each object’s information is stored at the terms describ- ing it. The information stored in a term is repeated along all its ancestors. Since the size of the description is D , and there are O (log T ) ancestors (assuming the ontology to be balanced), the storage cost is O ( D log T ) . The running time can be analyzed similarly. At the leaf level of the tree, there are D describing terms. When this O ( D ) information is sent up to the next level, the time required to combine the information is still O ( D ) since each object description is read only once and is matched using a hashtable to the information already computed. Assuming the height of the tree to be O (log T ) , the total running time is O ( D log T ) . 11