Patent ID: 8650163

Claim:
A method for estimating data reduction ratio for a data set, the method comprising: selecting a plurality of m elements from a data set comprising a plurality of N elements; associating an identifier h i for each of the plurality of m elements, where i is an integer between A and B, wherein B−A=m−1; associating an identifier h e for each of the plurality of elements in the data set, where e is an integer between C and D, wherein D−C=N−1; tracking number of times an element i appears in a base set that includes the plurality of m elements selected from the data set; calculating a value count i that indicates the number of times an identifier h e matches an identifier h i ; and estimating data reduction ratio for the plurality of N elements in the data set, based on number of m number elements selected from the data set and the value count i , wherein the selected plurality of m elements in the data set is stored in a base sample B; estimating of the data reduction ratio according to formula: Est = 1 m ⁢ ∑ i ∈ B ⁢ base i · ρ i count i , wherein ρ i defines a corresponding compression ratio for one or more of the selected plurality of m elements of the data set, and wherein the calculating and estimating are performed by one or more processors.