Most state-of-the-art object retrieval systems rely on ad-hoc similarities between histograms of quantised local descriptors to find, in their databases, all the images relevant to an image query. In this work, our goal is to replace those similarities with ones that are specifically trained to maximize the retrieval accuracy. We propose to use a simple and very general linear model whose weights directly represent the similarity values. We devise a variant of rank-SVM to learn those weights automatically from training data with fast convergence and we propose techniques to limit the number of parameters of the model and prevent overfitting. Importantly, the flexibility of our model allows us to seamlessly incorporate well-known image retrieval schemes such as burstiness, negative evidence and idf weighting, and still exploit inverted files for efficiency in the large-scale setting. In our experiments, we show that our approach consistently and significantly outperforms the similarities used in several state-of-the-art systems on 4 standard benchmark datasets. In particular, on the Oxford105k dataset, our method outperforms the closest competitor by 6%.