Images in a database or collection of images are each divided into multiple partitions with each partition corresponding to an area of an image. The partitions in an image may overlap with each other. Min-hash sketches are generated for each of the partitions and stored with the images. A user may submit an image and request that an image that is a partial match for the submitted image be located in the image collection. The submitted image is similarly divided into partitions and min-hash sketches are generated from the partitions. The min-hash sketches are compared with the stored min-hash sketches for matches, and images having partitions whose sketches are matches are returned as partial matching images.