Within the scope of information retrieval, efficient similarity search in large document or multimedia collections is a critical task. In this paper, we present a rigorous comparison of three different approaches to the image retrieval problem, including cluster-based indexing, distance-based indexing, and multidimensional scaling methods. The time and accuracy trade-offs for each of these methods are demonstrated on a large Corel image database. Similarity of images is obtained via a feature-based similarity measure using four MPEG-7 low-level descriptors. We show that an optimization of feature contributions to the distance measure can identify irrelevant features and is necessary to obtain the maximum accuracy. We further show that using multidimensional scaling can achieve comparable accuracy, while speeding-up the query times significantly by allowing the use of spatial access methods.