A database of images may be accessed. A feature set may be computed for each image, respectively. Each feature set includes feature integers quantized from interest points of a corresponding image. An initial set of clusters of the feature sets is found based on min hashes of the feature sets. Given the clusters of feature sets, descriptors for each of the clusters are computed, respectively, by selecting feature integers from among the feature sets in a cluster. The clusters are then refined by comparing at least some of the feature sets with at least some of the cluster descriptors, and based on such comparing adding some of the feature sets to clusters whose feature descriptors have similarity to the feature sets.