content_image/412984.jpg content_image/412985.jpg
<img src='content_image/412984.jpg'>

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

lower than this distance will be analyzed. For the NextEs- timate method, the distance of the best-pair is computed progressively, thereby saving on full AvgDist computa- tions as compared to the Complete method, which finds the actual distance of the best-pair. 

## 7.13 Effect of N on AvgDist 

We next discuss the experimental results when the number of objects is varied. We first measure the effect of number of objects on the Build phase. From the analysis done in Section 6.4, we expect the running time to grow linearly with the size of the input information. Assuming that the number of describing terms for an object is constant, the size of the information is directly proportional to the num- ber of objects. The experiment shows that the scalability is indeed linear (graph not shown). 

The next experiment (Figure 15) shows that the number of pairs investigated grows at most quadratically with N . Since the objects are generated using the same random process, this is expected. 

## 7.14 Effect of T on AvgDist 

The next set of experiments measure the effect of the num- ber of terms T on the different components of the AvgDist algorithm. Figure 16 shows the time taken to complete the Build phase. Note that this phase takes the same amount of time regardless of the choice of the method for estimat- ing the distance of a pair. Since the build procedure is run at each node, the effect of T is linear. Further, as can be seen from the plot, when the number of objects increase, more information needs to be processed at each node and the running time increases linearly. 

The next experiment measures the number of pairs in- vestigated against different values of T . As shown in Sec- tion 7.13, the number of pairs depends primarily on the distribution of the objects on the tree—mainly the num- ber of objects falling in the single span lists—and not on the size of the tree. Consequently, the size of the tree T has no appreciable effect. Similar to the previous set of experiments, this effect of T (or rather the lack of it) is directly reflected in the running time as well. The running time is essentially independent of T (graph not shown). 

## 8 Conclusions 

In this paper, we proposed the problem of finding top- k most similar object pairs annotated with terms from an ontology . The terms represent concepts and the objects are described using these concepts. The join problem ex- posed the computational aspects of the domain well. 

We then defined and motivated three object distances that can be used to define the dissimilarity (or, equiva- lently similarity) between a pair of objects. The minimum pairwise distance is useful in order to search objects that share a similar term. The average pairwise distance cap- tures the notion of similarity when the object definitions are imprecise or when objects need to be compared on multiple attributes. The third one, earth mover’s distance , is particularly useful as it finds the best way of matching terms in one object with those in the other by capturing the term-to-term relationships, and measures the distance corresponding to this best matching. 

Finally, we designed algorithms to efficiently solve the problem using all the above distance measures. The al- gorithm for EMD uses L 1 distance as a lower bound and even avoids all L 1 computations by modifying the thresh- old algorithm. The algorithm that solves the problem for the minimum pairwise distance runs in O ( D + Tk log k ) time. For the average pairwise distance, we devised a best-first search strategy that avoids all pairs investigat ion by generating lower bounds in an ordered manner. Ex- 

