A method and a processing device may be provided for performing efficient weighted consistent sampling. A group of sets having multiple elements with associated weights may be provided. A single hash function may be applied to each of the elements of the group of sets to produce consistent uniformly distributed non-negative random numbers. Transformed values corresponding to each of the elements may be produced by determining a wth root of a value based on applying the hash function to a respective element, where w may be based on a weight associated with the respective element. A minimum transformed value or a maximum transformed value may be determined for each of the sets. Sets having matching ones of the minimum transformed value or the maximum transformed value may be determined. The determined sets may be considered to be similar.