Systems and methods for data deduplication by generating similarity metrics using sketch computation

Abstract

A method for data reduction may comprise computing (i) a first sketch of a first segment and (ii) a second sketch of a second segment. The first sketch and the second sketch may each comprise a set of features that are representative of or unique to the corresponding first and second segments. The method also comprise processing the first sketch and the second sketch to generate a similarity metric indicative of whether the second segment is similar to the first segment. The method may further comprise (1) performing a differencing operation on the second segment relative to the first segment when the similarity metric is greater than or equal to a similarity threshold, or (2) storing the first segment and the second segment in a database without performing the differencing operation when the similarity metric is less than the similarity threshold.

1 . (canceled) 
     
     
         2 . A computer-implemented method for data processing based on variable segment sizing, comprising:
 (a) receiving a first input data stream and information about a target segment size;   (b) applying a hash function to the first input data stream to identify a natural break in the first input data stream, and identifying a chunk based at least in part on the natural break; and   (c) identifying a segment by i) repeating (b) and ii) summing up lengths of a first set of chunks to determine whether a sum of the lengths falls within the target segment size.   
     
     
         3 . The computer-implemented method of  claim 2 , wherein the natural break is identified by using a sliding window and applying the hash function to the sliding window to generate a region hash. 
     
     
         4 . The computer-implemented method of  claim 3 , wherein the sliding window has a size of 4-16 kB. 
     
     
         5 . The computer-implemented method of  claim 3 , wherein the region hash is a rolling hash. 
     
     
         6 . The computer-implemented method of  claim 2 , further comprising computing a first sketch of the segment comprising a set of features that are representative of or unique to the segment. 
     
     
         7 . The computer-implemented method of  claim 6 , wherein the set of features are computed using a first subset of chunks selected from the first set of chunks. 
     
     
         8 . The computer-implemented method of  claim 7 , wherein the set of features are computed based on a plurality of hashes of the first subset of chunks. 
     
     
         9 . The computer-implemented method of  claim 8 , wherein the plurality of hashes are generated using one or more hashing algorithms selected from the group consisting of Secure Hash Algorithm 0 (SHA-0), Secure Hash Algorithm 1 (SHA-1), Secure Hash Algorithm 2 (SHA-2), and Secure Hash Algorithm 3 (SHA-3). 
     
     
         10 . The computer-implemented method of  claim 6 , further comprising receiving a second sketch of a reference segment. 
     
     
         11 . The computer-implemented method of  claim 10 , further comprising processing the first sketch and the second sketch to generate a similarity metric indicative of whether the segment is similar to the reference segment. 
     
     
         12 . The computer-implemented method of  claim 11 , further comprising when the similarity metric is equal to or greater than a similarity threshold, performing a differencing operation on the segment and the reference segment to determine a difference between the segment and the reference segment at a chunk level. 
     
     
         13 . The computer-implemented method of  claim 12 , wherein the differencing operation comprises: receiving a reference set of hashes of the reference segment and generating a second set of hashes based on the first set of chunks, and comparing the first set of hashes to the reference set of hashes in a sequential order. 
     
     
         14 . The computer-implemented method of  claim 13 , wherein the first set of hashes are weak hashes. 
     
     
         15 . The computer-implemented method of  claim 13 , wherein the reference set of hashes are generated based on a set of chunks of the reference segment and are stored in a memory table. 
     
     
         16 . The computer-implemented method of  claim 15 , wherein the reference set of hashes are generated using a hashing algorithm selected based at least in part on the similarity metric. 
     
     
         17 . The computer-implemented method of  claim 16 , wherein a hashing strength of the hashing algorithm is selected based at least in part on the similarity metric. 
     
     
         18 . The computer-implemented method of  claim 12 , wherein the similarity threshold is at least 50%. 
     
     
         19 . The computer-implemented method of  claim 11 , further comprising when the similarity metric is less than a similarity threshold, storing the segment in a database without performing a differencing operation. 
     
     
         20 . The computer-implemented method of  claim 2 , wherein the target segment size ranges from 1 megabyte (MB) to about 16 MB. 
     
     
         21 . The computer-implemented method of  claim 2 , wherein the first set of chunks have variable lengths depending on the natural break.