Weighted features associated with a document are scaled using scales to generate a set of unweighted elements for each scale. A sketch is generated for each scale by sampling the unweighted elements generated for the scale. The scales are chosen based on a selected cutoff factor so that documents that have a similarity that is less than the cutoff factor might have no scales in common, while documents that have a similarity that is greater than the cutoff factor will have at sufficiently many but at least one scale in common. The similarity of these documents can be estimated using the sketches associated with each of the documents for the common scales.