content_image/414208.jpg content_image/414210.jpg content_image/414211.jpg content_image/414209.jpg
<img src='content_image/414208.jpg'>

<img src='content_image/414210.jpg'>

## 7.4 Effect of N on EMD 

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. 

## 7.5 Number of Object Pairs for EMD 

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 %. 

## 7.6 Effect of T on EMD 

The next experiment measures the effect of the total num- ber of terms on the EMD computations. Since both the 

<img src='content_image/414211.jpg'>

<img src='content_image/414209.jpg'>

L 1 and EMD-reduced depends only on the reduced num- ber of terms, the effect of T is minimal (graph not shown). 

## 7.7 Effect of t on EMD 

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 set of experiments measure the effect of dif- ferent parameters on the MinDist algorithm. 

