Appendix A Average pairwise distance follows triangular inequality B Hashing Figure 17: The Build phase of the AvgDist algorithm. Lemma 1. The average pairwise distance d$_{avg}$ as defined in Eq. (2) follows the triangular inequality property. Consider any term a$_{i}$ ∈ A , b$_{j}$ ∈ B , and c$_{k}$ ∈ C . Since the term distance function is a metric, we can write d ( a$_{i}$, b$_{j}$ ) + d ( b$_{j}$, c$_{k}$ ) ≥ d ( c$_{k}$, a$_{i}$ ) . Adding the | A | . | B | . | C | equations together yields Proof. Assume any three objects A , B and C . We need to prove that d$_{avg}$ ( A, B ) + d$_{avg}$ ( B, C ) ≥ d$_{avg}$ ( C, A ) . Dividing by | A | . | B | . | C | , we get or, | C | .$^{|}$$^{A}$$^{|}$$^{,}$$^{|}$$^{B}$$^{|}$ ∑ i,j =1 d ( a$_{i}$, b$_{j}$ ) + | A | .$^{|}$$^{B}$$^{|}$$^{,}$$^{|}$$^{C}$$^{|}$ ∑ j,k =1 d ( b$_{j}$, c$_{k}$ ) If L 1 is computed on all the terms in the TA phase of the EMD algorithm, then the time required for sorting of N objects in the initial phase can be saved. The key is to observe that all values for an object will be of the form 1 /c where c is the count of the number of terms in the object. Since c is at most T , a hashtable of size T with keys 1 $_{1}$, . . . , 1 T can be maintained. The N object values will be hashed into it. The heap H will be filled up with values of the form 1 i − 1 i +1 only. This requires a running time of O ( N + T ) instead of O ( N log N ) . When reduced number of terms are used, the values will be of the form t$_{1}$ $_{t$_{2}$}$, where 1 ≤ t 1 ≤ T and 1 ≤ t 2 ≤ T . This requires a running time of O ( N + T $^{2}$) . C Algorithm AvgDist-Build Algorithm AvgDist-Build Input: Node t Output: Object list B 1. L := list of objects in t 2. B := Modify( L ) 3. c := number of children of t 4. for i = 1 to c 5. CB [ i ] := AvgDist-Build( t.child [ i ] ) 6. for each co ∈ CB [ i ] 7. if ∃ o := Find( co.id , B ) 8. o.dist := o.dist + co.dist + co.count × t.edge [ i ] 9. o.count := o.count + co.count 10. end if 11. end for 12. end for | A | , | B | , | C | ∑ i,j,k =1 d ( a$_{i}$, b$_{j}$ ) +$^{|}$$^{A}$$^{|}$$^{,}$$^{|}$$^{B}$$^{|}$$^{,}$$^{|}$$^{C}$$^{|}$ ∑ i,j,k =1 d ( b$_{j}$, c$_{k}$ ) ≥ | A | , | B | , | C | ∑ i,j,k =1 d ( c$_{k}$, a$_{i}$ ) d$_{avg}$ ( A, B ) + d$_{avg}$ ( B, C ) ≥ d$_{avg}$ ( C, A ) ≥ | B | .$^{|}$$^{C}$$^{|}$$^{,}$$^{|}$$^{A}$$^{|}$ ∑ k,i =1 d ( c$_{k}$, a$_{i}$ ) 17