content_image/381279.jpg content_image/381281.jpg content_image/381280.jpg
<img src='content_image/381279.jpg'>

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

## 7.8 Effect of k on MinDist 

The first set of experiments measure the effect of th e num- ber of top pairs queried ( k ), on the running time of the MinDist algorithm. As shown in Figure 11, the scala- bility of MinDist with k is linear. The analysis d one in Section 5.1 shows that for small values of k , this is the ex- pected behavior. The largest real dataset—GO proc ess— finishes in less than 1 s for k ≤ 50 , demonstrating the effectiveness of the algorithm. 

## 7.9 Effect of T on MinDist 

We next report the effect of the number of terms T on the running time. Figure 12 shows that increasing T in- crements the running time of MinDist linearly, indepen- dent of the value of k . We also note the practicality of the MinDist algorithm. For a very large dataset of size N = 10 6 and a very large tree of size T = 10 $^{6}$, a top- 100 query finishes in about 100 s. For smaller k ’s and for smaller T ’s, the running time is in seconds. 

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

## 7.10 Effect of N on MinDist 

The running time analysis of the MinDist algorithm shows that it is independent of the number of objects N . When the number of terms T is kept constant, the experiments confirm that the running time is practically constant even when N is increased from 10 3 to 10 6 (graph not shown). 

The next set of experiments evaluate the performance of the two variants of AvgDist. 

## 7.11 Effect of k on AvgDist 

The first experiment on AvgDist illustrates the effect of k on the running time of the Build phase and the two differ- ent variants—NextEstimate and Complete—for the two larger GO datasets. All the six curves in Figure 13 are rel- atively flat, showing that the effect of k is minimal. Intu- itively, the running time of AvgDist depends on the actual number of object pairs investigated. For the GO datasets, even for even large k ’s up to 100 , this remains almost con- stant. Moreover, the Build phase takes negligible time in comparison to the Query phase. 

## 7.12 Number of Object Pairs for AvgDist 

We further investigated the effect of k by measuring the number of object pairs that are examined in the Query phase of the AvgDist algorithm. For this, we increased k up to 10000 . Figure 14 shows that η (i.e., the ratio to the total number of possible pairs) increases very slowly with k . The results are robust across different values of T (as shown in the figure) and N (not shown). This is the reason why the running time is also constant across k . 

The NextEstimate method examines less than 2% of the total number of pairs. The Complete method inves- tigates more object pairs (about 7%) than the NextEsti- mate method. Computing a distance for the current best- pair guarantees that only those pairs which have a bound 

