In the context of content-based image retrieval from large databases, traditional systems typically compute a single descriptor per image based for example on color histograms. The result of a query is in general the images whose descriptors are the closest to the descriptor of the query image. Systems built this way are able to return images that are globally similar to the query image, but can not return images that contain \emphsome of the objects that are in the query. Recent advances in image processing techniques, however, make this possible by computing local descriptors that are well suited for detecting similar objects in images. Obviously powerful, this fine-grain image recognition also changes the way the retrieval process is performed: instead of submitting a single query to retrieve similar images, multiple queries must be submitted, their partial results post-processed before delivering the answer. This paper first presents a family of local descriptors that support fine-grain image recognition. Our technique is robust: it detects similar objects in color images despite orientation changes (rotation of objects), translations, resolution changes, illumination variations, and partial occlusions. Many multi-dimensional indexes have been proposed to speed-up the retrieval process. These indexes, however, have been mostly designed for and evaluated against image databases where each image is described by a single descriptor. While this paper does not present any new indexing scheme, it shows that the three most efficient indexing techniques known today are still too slow to be used in practice with local descriptors because of the changes in the retrieval process.