7.4 Effect of N on EMD 7.5 Number of Object Pairs for EMD 7.6 Effect of T on EMD 7.7 Effect of t on EMD 13 L 1 and EMD-reduced depends only on the reduced num- ber of terms, the effect of T is minimal (graph not shown). As the number of children of root, i.e., t increases, the complexity of the TA increases linearly. Figure 10 shows the running times for varying t . The size of each object description is limited to 10 . When t ≤ 10 , the time in- creases. The EMD-reduced behaves in the opposite man- ner. This is due to the interaction of two opposing effects: as t increases, each computation takes more time, but the lower bound gets tighter as more number of terms are taken into account resulting in less number of full EMD computations. However, when t > 10 , since there are at most 10 terms in each object, the object description size do not get reduced and each EMD-reduced computation takes as much time as the full EMD computation. Since O ( N $^{2}$) of these computations are performed, the running time shoots up. The L $_{1}$-reduced, on the other hand, shows only a little increase. The next experiment measures the effect of the total num- ber of terms on the EMD computations. Since both the To check the effect of increasing N , we measured the ra- tio of object pairs for which full EMD computation was done. The ratio was measured as number of pairs investi- gated to the total number of possible pairs ( N ( N − 1) / 2 ) and is denoted by η . As Figure 9 shows, η decreases when N is increased. For N = 250 , the number of EMD com- putations becomes lower than 10 %. Figure 8 shows that the scalability of our algorithm with N is better than quadratic. Even though the number of objects increases quadratically, due to L 1 lower bounding, many of the object pairs are pruned. Consequently, the number of full EMD computations increases by a lower factor. Also, even for N = 350 which translates to 6 × 10 4 object pairs, our algorithm finishes in only 55 s. Figure 8: Effect of N on EMD. Figure 10: Effect of t on EMD. Figure 9: Ef fect of N on number of pairs examined for EMD. Figure 7: Effect of k on EMD.  1  10  100  1000  10000  0  5  10  15  20  25 Running time (s) k EMD: GO Localization EMD reduced L$_{1}$  reduced  0  50  100  150  200  250  0  5  10  15  20  25 Running time (s) t EMD: Synthetic dataset, N=50, T=2.5x10$^{2}$, k=5 EMD reduced L$_{1}$ reduced  0  200  400  600  800  1000  1200  1400  50  100  150  200  250  300  350 Running time (s) N EMD: Synthetic dataset, T=2.5x10$^{2}$, k=5 EMD reduced L$_{1}$  0  0.1  0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9  1 50  100  150  200  250  300  350 Ratio of pairs to N(N-1)/2,  N EMD: Synthetic dataset, T=2.5x10$^{2}$, k=5 EMD reduced L$_{1}$ The next set of experiments measure the effect of dif- ferent parameters on the MinDist algorithm.