Table 1: Minimum pairwise distances for the example in Figure 1. Table 3: EMDs for the example in Figure 1. Table 2: Average pairwise distances for the example in Figure 1. Min O 1 O 2 O 3 O 4 O 1 0.0 0.0 0.5 1.0 O 2 0.0 1.0 1.5 O 3 0.0 0.5 O 4 0.0 EMD O 1 O 2 O 3 O 4 O 1 - 1.25 1.75 1.75 O 2 - 2.17 2.50 O 3 - 2.00 O 4 - Avg O 1 O 2 O 3 O 4 O 1 1.25 1.50 2.08 1.75 O 2 0.75 2.17 2.50 O 3 1.11 2.00 O 4 0.50 3.2 Minimum Pairwise Distance 3.3 Average Pairwise Distance 3.4 Earth Mover’s Distance Definition 1 (Minimum Pairwise Distance) . The mini- mum pairwise distance between two objects O$_{i}$ and O$_{j}$ , denoted by MinDist , is defined as: This distance is useful when searching objects that have similar terms. For example, even though a single biolog- ical document may contain references to different terms like photoreceptor cells and ganglion cells, it is useful to be able to retrieve it when another document that de- scribes photoreceptor cells is queried. This distance is of particular use in keyword search- ing , where the query document consists of only the sin- gle keyword, and all documents having that keyword will be returned with a distance of 0. MinDist, in general, ex- tends this idea by finding additional documents that con- tain terms most similar to the queried keyword. The MinDist measure is heavily used in hierarchical bottom-up clustering methods where in each step, two clusters with the minimum pairwise distance are merged. It has also been successfully used for finding the distance between two genes, where a gene is annotated with a set of terms from GO [2]. Table 1 shows the MinDist measures among the ob- jects in Figure 1. MinDist is not a metric distance as it does not maintain the triangular inequality. For example, d$_{min}$ ( O 1 ,O 4 ) + d$_{min}$ ( O 1 ,O 2 ) = 1 . 0 + 0 . 0 < 1 . 5 = d$_{min}$ ( O 2 ,O 4 ) . Definition 2 (Average Pairwise Distance) . The average pairwise distance between two objects O$_{i}$ and O$_{j}$ , de- noted by AvgDist , is defined as: where | O$_{i}$ | and | O$_{j}$ | denote the number of terms describ- ing O$_{i}$ and O$_{j}$ respectively. The AvgDist is useful in cases where the objects are not precisely defined. For example, it has been success- fully used for gene function prediction using GO terms for yeast genes [14] as well as in the domain of web ser- vices [11]. The MinDist measure fails in such cases. Table 2 shows the AvgDist measures among the objects in Figure 1. AvgDist is not a metric, as it fails to satisfy the identity property, i.e., d$_{avg}$ ( x,x ) can be greater than 0 (e.g., d$_{avg}$ ( O 1 ,O 1 ) = 1 . 25 ). However, since it follows symmetry and triangular inequality$^{2}$, it can be considered as a pseudo-metric distance. Apart from the property of not being a true metric, AvgDist also suffers from the fact that each term in one object is matched with every other term in the other ob- ject. For example, consider two documents with the terms { war, sports } and { war, football } . Even though it is obvious that the distance between these two docu- ments should be small, the average distance unnecessarily compares “war” in the first document with “football” in the other. The earth mover’s distance (EMD) [12] rec- tifies this shortcoming by comparing only the like terms through finding the best matching between the terms of the two documents. For this example, EMD will match “war” with “war” and “sports” with “football” and aggre- gate these distances only. EMD has been shown to be better than other distances in finding similar documents using the WordNet ontology [19]. Formally, each object is considered to be composed of “mass” at the specific spatial locations (corresponding to the terms that describe the object) in the ontology. The total mass of each object is 1 ; consequently, the mass at $^{2}$See Appendix for the proof. 4 d$_{avg}$ ( O$_{i}$,O$_{j}$ ) = 1 | O$_{i}$ | . | O$_{j}$ | ∑ t$_{i}$ ∈ O$_{i}$,t$_{j}$ ∈ O$_{j}$ d ( t$_{i}$,t$_{j}$ ) (2) d$_{min}$ ( O$_{i}$,O$_{j}$ ) = min t$_{i}$ ∈ O$_{i}$,t$_{j}$ ∈ O$_{j}$ { d ( t$_{i}$,t$_{j}$ ) } (1)