## 6 Similarity Searching Methods and Computational Efficiency
The results showed that using a relatively large reference database with 2522 ROIs, all three distance metric learning methods generated higher performance levels than using the Euclidean distance based measurement in classifying between ROIs depicting either malignant masses or benign masses and normal breast tissue with CAD-cued false-positive regions. Among three distance metric learning methods, the boosted distance metric learning method was superior to two other methods. Although the CBIR algorithms implemented in CAD schemes share many common approaches and requirements of CBIR algorithms used for other applications (i.e., biomedical informatics or PACS), CAD schemes requires much higher computational efficiency. Thus, some of effective techniques commonly used in other types of CBIR approaches (i.e., relevance feedback [81; 84]) are not suitable for CAD. To make the system acceptable in the routine clinical practice, the CAD scheme must produce the detection and/or diagnostic results in \"real-time\" (i.e., less than one or two seconds) after the observer queries a suspicious ROI. As the rapid increase of the size of the clinical medical image databases (i.e., more than 12,000 digital medical images produced per day at the RadiologyDepartment of one University Hospital [11]), developing more efficient searching method is an important and practical issue in developing CAD schemes using CBIR approach. Since CAD generates the detection or classification results for each queried ROI only based on a small number of retrieved \"similar\" reference ROIs, extensively searching for and comparing all reference ROIs stored in the reference database wastes the majority of processing time and substantially increases the computational cost. Besides the selection of computationally efficient image features, another effective approach to reduce computational cost is to make CBIR algorithm enable to early discard a substantial fraction of un-related (low-correlated) ROIs to the queried ROI before conducting the detailed similarity comparison using a multi-feature based distance metric. One research group developed and reported a special metric access method (MAM) to search for the similar reference ROIs. The method used a distance function to organize the reference ROIs in a tree-like scheme that allows the use of the triangular inequality property to prune subsets of ROIs that do not need to be compared with the queried ROI. The study demonstrated that using this method CBIR scheme could early discard a large fraction of un-related ROIs and provided fast and more effective retrieval of the similar reference ROIs to the queried ROI [85]. In the CAD schemes, another popular approach is to add a prescreening step using one or two texture or morphological features. For example, using the fractal dimension as a prescreening feature to early discard all reference ROIs in which the difference of their fractal dimension to the queried ROI is larger than the predetermined threshold, one study showed that at least 53% of reference ROIs could be early discarded for all 3000 queried ROIs without reducing the overall CAD performance [69]. As the advance of computing technologies, researchers have also developed more powerful and user-friendly open-source frameworks that enable parallel execution of early discarding un-related reference images and conducting image similarity comparison among several reference databases. For example, a CBIR system has been developed (\"Diamond\" [86]), which embodies the new software architecture for rapidly scanning large volumes of distributed data and filtering the data with domain-specific software (i.e., CAD schemes). The key concept of the \"Diamond\" architecture is the concept of early discard: the ability to reject irrelevant data (or reference ROIs) very close to their point of storage, thus creating low data transmission overhead in executing CBIR algorithm for similarity comparison [87]. This system has been applied and tested in a number of CBIR applications including CAD of mammograms [83].