Patent ID: 8935222
Filing Date: 2015-01-13
Classification: G06F

Abstract:
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 a globally optimal subset of a 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; applying the optimal calculation operation individually on each sequence of the matching segments that are surrounded on both ends of the matching segments by two of the non-matching segments where the non-matching segment cannot be altered; splitting a sequence of the matching segments into sub-parts for obtaining the 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; and 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.