Abstract : One of the main limitations of image search based on bag-of-features is the memory usage per image, limiting to a few million the size of the dataset that can be handled on a single machine in a reasonable response time. In this paper, we first show that these limitations can be somewhat reduced by using index compression. Then, we propose an image representation obtained by projecting bag-of-features histograms onto a set of predefined sparse projection functions, producing several image descriptors. Coupled with a proper indexing structure, an image is represented by a few hundred bytes. A distance expectation criterion is then used to rank the images. Our method is at least one order of magnitude faster than standard bag-of-features while providing excellent search quality.