Patent ID: 8799238

Claim:
A method for data deduplication, comprising: receiving a set of hashes, wherein each hash of the set of hashes is derived from a data chunk of a set of input data chunks; sampling the set of hashes based on a set value for each of a predetermined number of bits in a string of hash bits, to form a sampled set of hashes; using an index, identifying data chunk containers that hold data chunks having a hash in the sampled set of hashes; loading indexes having the sampled set of hashes for at least one of the identified data chunk containers into a memory; determining which of the hashes in the set of the input data chunks correspond to the data chunks stored in data chunk containers corresponding to the loaded indexes; deciding which of the set of input data chunks should be stored based at least in part on determining which of the hashes of the set of input data chunks correspond to the data chunks stored in data chunk containers corresponding to the loaded indexes; and storing the chunks of the set of input data chunks that have been decided to be stored in one or more data chunk containers.