A method for searching in a large-scale database of images for images that are visually similar to query images is provided using a processor to perform the following steps: computing visual features for the database images; constructing an Image Anchor Graph that contains a plurality of anchors corresponding to a subset of images in the database, according to the computed visual features; computing visual features for the query images; and retrieving database images similar to one or more user query images using a ranking algorithm that uses the anchors in the Image Anchor Graph according to the computed visual features of both the query images and the database images on the Image Anchor Graph.