## 6 Similarity Searching Methods and Computational Efficiency  
Another long-standing challenge in developing CBIR systems is the definition of a suitable distance function to measure the similarity levels between images in an application context which complies with the human perception of similarity. The most common types of queries based on image similarity are k-nearest neighbor and range queries. A k-nearest neighbor query involves searching for the \(k\) most similar reference ROIs to the queried ROI. A range query consists of searching for all reference ROIs similar to the queried ROI up to a given degree (or range) [63]. Current CAD schemes using CBIR approaches typically use the k-nearest neighbor type searching method. The CAD schemes force the CBIR algorithms to retrieve the fixed \(k\) \"most similar\" reference ROIs without considering the given degree of similarity level between the queried ROI and each of the retrieved reference ROIs. This can \begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline Threshold on Similarity Level & 0 & 0.1 & 0.2 & 0.3 & 0.4 & 0.5 & 0.6 & 0.7 & 0.8 & 0.9 \\ \hline Area under ROC Curve & 0.854 & 0.859 & 0.859 & 0.864 & 0.877 & 0.888 & 0.908 & 0.911 & 0.919 & 0.932 \\ \hline Standard Deviation & 0.004 & 0.004 & 0.005 & 0.007 & 0.008 & 0.011 & 0.011 & 0.014 & 0.016 & 0.016 \\ \hline \end{tabular}
\end{table} 
Table 2: The change of CAD performance as the increase of threshold values on the queried ROIs. be an issue that reduces the reliability of CAD-generated results including both clinical relevance of detection scores and visual similarity of retrieved reference ROIs. In the application of multi-feature based k-nearest neighbor (KNN) algorithm, one of the most popular and relatively effective methods to measure the similarity level between two compared ROIs is the Euclidean distance based measurement [33]. In this method, similarity is measured by the difference in feature values, \(f_{r}(x)\), between a queried ROI ( \(y_{q}\)) and a reference ROIs ( \(x_{i}\)) in a multi-dimensional (\(n\)) feature space. \[d(y_{q},x_{i})=\sqrt{\sum_{r=1}^{n}\left(f_{r}(y_{q})-f_{r}(x_{i})\right)^{2}} \tag{3}\]  
The smaller the difference (\"distance\"), the higher the computed \"similarity\" level is between the two compared ROIs. Although this approach is easy to implement and relatively robust, the limitation is that the distance between two instances (the queried ROI and the reference ROI) is calculated based on all attributes (the selected features) of the ROIs with equal weights. If the contribution of the selected features is not the same, this equally weighted Euclidean distance based measurement can generate misleading results [76]. To improve the performance and reliability of similarity measurement, a number of other advanced technologies or approaches have been investigated and tested. One type of approaches is using principal component analysis (PCA) [81] or minimum description length (MDL) [82] to reduce the dimensionality of feature space. Recently, one research group compared several supervised distance metric learning methods and investigated their feasibility and advantages when applying to the CBIR algorithms used in CAD scheme of mammograms [83]. In this framework, the feature data is supplemented by side information in the form of pairwise of \"similarity\" and \"dissimilarity\" relationship between two compared ROIs. The goal is to learn a distance function that achieves the optimal results in searching for the clinical relevant and feature similar ROIs. The researchers compared three learning methods namely, the global distance metric learning, local distance metric learning, and boosted distance metric learning.