Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for identifying similar images. In some implementations, a method is provided that includes receiving a collection of images and data associated with each image in the collection of images; generating a sparse feature representation for each image in the collection of images; and training an image similarity function using image triplets sampled from the collection of images and corresponding sparse feature representations.