Recent advances in processing and networking capabilities of computers have led to an accumulation of immense amounts of multimedia data such as images. One of the largest repositories for such data is the World Wide Web. There is an urgent need for systems which allow to search these vast on-line collections. We present Cortina, a large-scale image retrieval system for the World Wide Web. It handles over 3 Million images to date. The system retrieves images based on visual features and collateral text. Methods are introduced to investigate these multi-modal characteristics of the data and to gain insights into the semantics within the data. We show that a search process which consists of an initial query-by-keyword and followed by relevance feedback on the visual appearance of the results is possible for large-scale data sets. We also show that it is superior to the pure text retrieval commonly used in large-scale systems. The precision is shown to be increased by exploiting the semantic relationships within the data and by including multiple feature spaces into the search process.