Images are retrieved and ranked according to relevance to attributes of a multi-attribute query through training image attribute detectors for different attributes annotated in a training dataset. Pair-wise correlations are learned between pairs of the annotated attributes from the training dataset of images. Image datasets may then be searched via the trained attribute detectors for images comprising attributes in a multi-attribute query, wherein images are retrieved from the searching that each comprise one or more of the query attributes and also in response to information from the trained attribute detectors corresponding to attributes that are not a part of the query but are relevant to the query attributes as a function of the learned plurality of pair-wise correlations. The retrieved images are ranked as a function of respective total numbers of attributes within the query subset attributes.