Patent ID: 8527482

Claim:
A method of reducing redundancy between two or more data sets comprising: accessing a reference file comprising at least a plurality of data blocks, wherein the plurality of data blocks are hashed to identify duplicate data; creating an oversubscribed hash table comprising a plurality of hash entries, wherein the oversubscribed hash table is oversubscribed based on the plurality of data blocks in the reference file by at least an oversubscribed ratio of 10:1 wherein for at least every 10 data blocks in the reference file there is a single hash entry in the hash table; computing hash codes for the plurality of data blocks in the reference file and storing a subset of the hash codes in the hash entries in the oversubscribed hash table; accessing a current file comprising at least a plurality of data blocks; computing hash codes for a plurality of data blocks in the current file and comparing the hash codes associated with the current file to the hash entries in the oversubscribed hash table; identifying a first pair of matching hash codes where a first hash code of one of the data blocks in the current file matches a first hash code in one of the hash entries in the oversubscribed hash table; identifying a second pair of matching hash codes where a second hash code of one of the data blocks in the current file matches a second hash code of one of the hash entries in the oversubscribed hash table; and when the matching hash codes in the first and second pairs of matching hashes have a matching order and distance, comparing the data in the associated blocks of the current file and the reference file to identify a run of matching data in the current and reference files.