The invention pertains to a method and Information Handling System (IHS) for performing delta compression on probabilistically clustered chunks of data. From a source of chunks a corresponding sketch to represent each chunk is generated. Then, from the generated sketches a subset of similar sketches is determined using a probabilistic based algorithm. Finally, delta compression is performed on the chunks which are represented by the similar sketches in the determined subset.