Parallel Clustering Design And Implementation In Web Image Retrieval

With the development of network bandwith and image technology, there are more and more images on the Web, which constitute a huge Web image database. Web image retrieval helps users quickly and accurately access to the image information on the Web. Clustering technology was adopted to index Web images in Web image retrieval, which supplies quickly retrieval service for users. However, a large number of the existing clustering algorithms in dealing with large-scale data are less efficient and cannot meet the requirements of image clustering in the Web image retrieval.On the basis of the approximation algorithm for Earth Mover's Distance (abbr: EMD) and the dynamic adaptive image clustering algorithm, we propose the parallel algorithm of hierachical and adaptive image clustering (abbr: HAP), which overcomes the efficiency droping of the dynamic adaptive image cluster algorithm and makes full use of its advantages of processing Web images dynamicly.There are two factors in the performance of image clustering, which are I/O time and EMD match time. Global EMD match mechanism is adopted to integrate the clustering process which is available to the parallel clustering implementation, and memory mechanism is adopted to induce the I/O time. In the implementation of HAP, data parallel method is used to parallel the EMD match which induces the EMD match time, and the message mechanism is used to keep the consistence of the cluster feature tree (abbr: CF-tree) in all slave nodes and to merge the cluster result in the master node.Through the performance testing on system, HAP has improved the efficiency of the system evidently. Compared with the dynamic adaptive image clustering algorithm, HAP attains excellent speedup ratio. When 5, 10 and 20 CPU nodes are used, the speedup ratios are 3.5, 7.5 and 16 respectively.