1. A computer-implemented method comprising: under the control of one or more computer systems configured with executable instructions, calculating a cluster descriptor for each of a plurality of clusters of feature vectors, the feature vectors being calculated based at least in part on a plurality of feature points of a subset of a collection of images; creating a first histogram for at least one image of the subset of the collection of images, the first histogram having a plurality of bins that correspond to the clusters of feature vectors, the contents of the bins are based at least in part on the number of the feature vectors of the image that were mapped to the corresponding clusters, wherein the features vectors are mapped the nearest one of the clusters based at least in part on the cluster descriptors; creating a second histogram for at least one image of the subset of the collection of images, the second histogram having a plurality of bins that correspond to a plurality of radial-polar bins of a radial-polar grid positioned on an edge image of the image, the contents of the bins of the second histogram are based at least in part on a number of pixels of the edge image that are located in the corresponding radial-polar bins of the radial-polar grid; creating edge histograms for the images of the subset of the collection of images based on a plurality of feature associated with the edge images of the images, the edge histograms having a plurality of bins that correspond to a plurality of radial-polar bins of radial-polar grids that are positioned on the feature points associated with the edge images, the contents of the bins of the edge histograms are based at least in part on the number of pixels of the edge images that are located in the radial-polar bins of the radial-polar grids; creating a third histogram for at least one image of the subset of the collection of images, the third histogram having a plurality of bins that correspond to a plurality of edge-histogram clusters, the contents of each of the bins of the third histogram are based at least in part on the number of the edge histograms that were mapped to the corresponding edge-histogram cluster, wherein the edge histograms are mapped to the nearest one of the edge-histogram clusters based at least in part on a plurality of edge-histogram cluster descriptors that were calculated for each of the edge-histogram clusters; and identifying at least one image of the subset of the collection of images that is visually similar to a query image based at least in part on a comparison of first, second, and third histograms that characterize the query image and the first, second, and third histograms of the images of the subset of the collection of images.