METHOD AND APPARATUS TO PROCESS DATA BASED UPON ESTIMATED COMPRESSIBILITY OF THE DATA

• US 20130254441A1
• Filed: 03/20/2012
• Published: 09/26/2013
• Est. Priority Date: 03/20/2012
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: DROR, ITAI, KIPNIS, ALON
• Granted Patent: US 9,246,511 B2
• Time in Patent Office: Days
• US Class Current: 710/68
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3071 Prediction
• CPC Class Codes: H03M 7/3079 Context modeling
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

A method includes, in a data storage device, determining an estimated compression ratio. The estimated compression ratio is based on hash values of a subset of a data set. The method includes selectively processing the data set based on the estimated compression ratio prior to storage of data associated with the data set in a memory of the data storage device.

Claims

1. A method comprising:

in a data storage device, performing;

determining an estimated compression ratio, wherein the estimated compression ratio is based on hash values of a subset of a data set; and

processing the data set prior to storage of data associated with the data set in a memory of the data storage device, wherein the processing is determined based on the estimated compression ratio.

2. The method of claim 1, wherein the subset includes fewer data elements than a total number of data elements in the data set.

3. The method of claim 1, further comprising determining whether to initiate a compression operation of the data set at a compressor of the data storage device based on comparing the estimated compression ratio to a threshold value.

4. The method of claim 3, wherein the hash values are generated at hash circuitry, and wherein initiating the compression operation includes generating additional hash values of the data set at the hash circuitry.

5. The method of claim 3, wherein a determination is made to initiate the compression operation in response to the estimated compression ratio being less than the threshold value.

6. The method of claim 3, wherein a determination is made to refrain from initiating the compression operation in response to the estimated compression ratio satisfying the threshold value.

7. The method of claim 1, wherein each hash value is determined from a corresponding sample of the data set, each sample including at least two data elements.

8. The method of claim 1, further comprising selecting, based on the estimated compression ratio, a type of error correction code encoding to apply to a representation of the data set.

9. The method of claim 1, wherein the estimated compression ratio is determined based on a count of collisions of the hash values.

10. The method of claim 9, wherein the estimated compression ratio is further based on a comparison of the count of collisions to an expected number of collisions based on a uniform distribution of data values.

11. The method of claim 1, further comprising applying, by a processor, a selected hash function to a plurality of data elements of the data set to determine the hash values of the subset of the data set.

12. A data storage device comprising:

a memory configured to store a data set, the data set including a first plurality of data elements; and

processing hardware configured to;

determine an estimated compression ratio associated with the data set based on hash values of a subset of the data set; and

selectively process the data set based on the estimated compression ratio to produce a representation of the data set prior to storage of data associated with the data set in a the memory of the data storage device.

13. The data storage device of claim 12, wherein the processing hardware is further configured to determine, based on comparing the estimated compression ratio to a threshold value, whether to initiate a compression operation of the data set at a compressor of the data storage device.

14. The data storage device of claim 13, wherein the processing hardware includes a comparator to initiate the compression operation in response to the estimated compression ratio being less than the threshold value.

15. The data storage device of claim 13, wherein the processing hardware includes a comparator, the comparator to refrain from initiating the compression operation in response to the estimated compression ratio satisfying the threshold value.

16. The data storage device of claim 12, wherein each of the hash values is determined from a corresponding sample of the data set, each sample including at least two data elements.

17. The data storage device of claim 12, further comprising an error correction coding (ECC) encoder, and wherein the processing hardware is configured to select, based on the estimated compression ratio, a type of error correction code encoding to be applied by the ECC encoder to a representation of the data set.

18. The data storage device of claim 12, wherein the estimated compression ratio is further based on a comparison of a count of collisions to an expected number of collisions based on a uniform distribution of data elements.

19. The data storage device of claim 12, wherein the processing hardware is further configured to apply a selected hash function to a plurality of data elements of the subset of a data set to determine the hash values.

20. The data storage device of claim 12, wherein the subset includes fewer data elements than the data set.