Patent ID: 9626374
Date: 2017-04-18
CPC Classifications: G06F

Claim:
1. A method for optimizing a partition of a data block into matching and non-matching segments in data deduplication using a processor device in a computing environment, the method comprising: applying an optimal calculation operation in polynomial time to the matching segments for selecting the globally optimal subset of the set of the matching segments according to overhead considerations for minimizing an overall size of a deduplicated file by determining a trade off between a time complexity and a space complexity, wherein applying the optimal calculation operation to the matching segments determines which of the matching segments should be preserved; splitting a sequence of the matching segments into sub-parts for obtaining a globally optimal subset; applying the optimal calculation operation on the sub-parts of the matching segments; combining solutions of the optimal calculation operation of the sub-parts into the optimal calculation operation for an entire range of the sequence of the matching segments; building the globally optimal subset by means of a first two-dimensional table represented by a matrix C[i,j], and storing a representation of the globally optimal subset in a second two-dimensional table represented by a matrix PS[i,j] that holds, at entry [i,j] of the matrix, the globally optimal subset for a plurality of parameters in form of a bit-string of length j−i+1, wherein i and j are indices of bit positions corresponding to segments; and declaring each of the matching segments that are determined not to be preserved as new segments added to the non-matching segments;