This paper deals with content-based image indexing and category retrieval in general databases. When large categories are searched, systems must explore the database. We introduce an interactive retrieval strategy designed for database exploration. The technique is based on a compound query and a dedicated similarity function. The usual strategy based on a similarity score ranking is replaced by a stochastic image selection process. A competition between feature spaces for the similarity measure refinement is also included in the strategy. A quality assessment is realized on a general database of 6.000 images in order to illustrate and validate our approach.