Figure 4: The EMD algorithm. 4.3 Algorithm 4.4 Analysis of Time Complexity 5 The Algorithm for MinDist Algorithm EMD Input: Reduced object list O with t terms Output: Object pair list P 1. for dimension j = 1 to t 2. Sort O$_{ij}$ (only j th dimension) 3. Insert N − 1 differences into heap H [ j ] 4. List C [ j ] := Φ 5. Thresholds τ [ j ] := 0 6. end for 7. P := Φ ( ∴ P.dist (i.e., k th distance in P ) := ∞ ) 8. Threshold R := sum of all τ [ j ] (therefore, R := 0 ) 9. j := 0 10. while R < P.dist 11. Extract minimum pair p from H [ j ] 12. τ [ j ] := difference for pair p 13. if p is not seen earlier 14. d 1 := L 1 on t terms of p 15. if d 1 ≤ P.dist 16. d 2 := L 1 on all terms of p 17. if d 2 ≤ P.dist 18. d 3 := EMD on all terms of p 19. if d 3 ≤ P.dist 20. Insert p into P 21. Update P.dist as new k th distance 22. end if 23. end if 24. end if 25. end if 26. Update R using τ [ j ] 27. Scan C [ j ] with p to generate new pairs Γ 28. Add Γ to H [ j ] 29. j := ( j + 1) mod t 30. end while Figure 4 summarizes the entire EMD algorithm that uses TA with the lower bounding strategy. First, the L 1 lower bound using reduced number of terms is extracted from the heap (line 14). If it is less than the current k th es- timate P.dist in P (line 15), the bound is improved by computing the L 1 using all the terms (line 16). If it still less (line 17), the exact EMD is computed (line 18) and the top- k list is modified, if necessary (line 21). For each such L $_{1}$-reduced computation, the threshold distance ( R ) is increased. When R > k th distance in P , no other ob- ject pair can have L $_{1}$-reduced distance less than the top- k pairs already found. Therefore, the EMD distances will also be greater. Hence, the algorithm is then halted. For each of the t dimensions, we incur the following cost. Initially, sorting takes O ( N log N ) time. 7 Thereafter, inserting the N − 1 elements in the heap takes O ( N ) time. With each call to the heap, an extract operation takes O (log N ) . At the i th iteration, at most i elements are added to the heap again. This takes O ( i log N ) time. Thus, if we have k ′ calls (this k ′ is generally larger than k as many object pairs with low lower bound but high EMD are examined), the time per dimension is O ( k ′ 2 log N ) which leads to a total time of ∑ t j $_{=1}$O ( k ′ 2 j log N ) or O ( tk ′ 2 max log N ) where k$_{max}$ is the maximum of all k ′ $_{j}$s. Space Complexity: Heap j requires O ( N + k ′ 2 j ) space where k ′ j is the number of calls made on column j . Hence, the total space required is O ( t ( N + k ′ 2 $_{max}$)) where k ′ max is the maximum of k ′ $_{j}$’s. Unlike the d$_{emd}$ distance, whenever two terms corre- sponding to two objects are encountered, the MinDist for the object pair can be estimated. If it is better than the cur- rent estimate, it is retained; otherwise, it is never needed again. We next explain the MinDist algorithm that ex- ploits this property. Any object pair ( O$_{i}$, O$_{j}$ ) having a lesser distance than ( O$_{g}$, O$_{h}$ ) must have a term pair ( t$_{i}$ ∈ O$_{i}$, t$_{j}$ ∈ O$_{j}$ ) which has a lesser distance than any term pair ( t$_{g}$ O$_{g}$, t$_{h}$ ∈ O$_{h}$ ) . Hence, we only need to identify such term pairs ( t$_{i}$, t$_{j}$ ) that are close and process their inverted lists, i.e., the list of objects. $^{7}$An alternative approach using hashing that may reduce this time is discussed in Appendix. 7 A pre-processing step is required to build the inverted lists of objects at each node. The inverted index is needed to be built for the minimum and average pairwise dis- tances but not the earth mover’s distance. For each object O$_{i}$ , when a term t$_{j}$ appears in it, O$_{i}$ is inserted into the inverted list of t$_{j}$ . The list is accessed using hashing, and the object is inserted at the top of list. Figure 5 describes the entire algorithm. For a node, the MinDist algorithm computes the top- k object pairs that are described by at least one term pair in its subtree. Any such object pair must either (i) be in the top- k list of the children, or (ii) contains terms from different subtrees of the children. The recursive definition of the first kind al- lows us to employ a divide-and-conquer approach. For the