PREDICTING DATA COMPRESSIBILITY USING DATA ENTROPY ESTIMATION

• US 20140244604A1
• Filed: 02/28/2013
• Published: 08/28/2014
• Est. Priority Date: 02/28/2013
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Oltean, Paul Adrian, Knig, Arnd Christian, Li, Jin, Sengupta, Sudipta, Mehrotra, Sanjeev, Rusu, Cosmin A., Manasse, Mark Steven
• Application Number:
  US13/781,663
• Publication Number:
  US 20140244604A1
• Time in Patent Office: Days
• US Class Current: 707/693
• 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/3091 Data deduplication

Abstract

The subject disclosure is directed towards predicting compressibility of a data block, and using the predicted compressibility in determining whether a data block if compressed will be sufficiently compressible to justify compression. In one aspect, data of the data block is processed to obtain an entropy estimate of the data block, e.g., based upon distinct value estimation. The compressibility prediction may be used in conjunction with a chunking mechanism of a data deduplication system.

Claims

1. In a computing environment, a method, comprising, processing data of a data block to predict compressibility of the data block, including obtaining an entropy estimate corresponding to the data block, determining whether the entropy estimate of the data block is high, and if not, outputting compressibility information that indicates that the data block is predicted to be sufficiently compressible.

2. The method of claim 1 wherein obtaining the entropy estimate comprises estimating a number of distinct values in the data block, and wherein determining whether the entropy estimate of the data block is high comprises evaluating the number of distinct values against a threshold level.

3. The method of claim 2 wherein estimating the number of distinct values comprises performing at least one hash function on at least some of the data of the data block to obtain the number of distinct values.

4. The method of claim 1 further comprising, obtaining the entropy estimate by generating hash values via a plurality of hash functions on at least some of the data of the data block, maintaining representations of the hash values, and processing the representations of the hash values to estimate the number of distinct values in the data block.

5. The method of claim 4 wherein maintaining representations of the hash values comprises maintaining a structure that holds an approximation of accumulated information.

6. The method of claim 1 wherein obtaining the entropy estimate of the data block comprises sampling less than all of the data of the data block.

7. The method of claim 1 wherein obtaining the entropy estimate of the data block comprises performing uniform sampling or non-uniform sampling, or a combination of uniform sampling and non-uniform sampling.

8. The method of claim 1 wherein obtaining the entropy estimate of the data block comprises inferring the compressibility of a chunk based on interpolation or extrapolation of sampled entropy.

9. The method of claim 1 further comprising, determining sampling parameters based at least in part on a file format.

10. The method of claim 1 further comprising, selecting a compression algorithm or no compression based at least in part upon the compressibility information.

11. In a computing environment, a system comprising, a chunking mechanism of a deduplication system, the chunking mechanism configured to chunk data for storage in a chunk store, the chunking mechanism coupled to or incorporating a compression prediction mechanism, the compression prediction mechanism configured to process at least some of the data in a chunk to obtain an estimate of compressibility of the chunk based upon a data entropy estimation.

12. The system of claim 11 wherein the compression prediction mechanism performs entropy estimation based upon distinct value estimation via at least one hash algorithm that hashes the at least some of the data in the chunk into representative values maintained in at least one data structure, and wherein the compression prediction mechanism uses the representative values in each data structure to obtain the estimate of compressibility of the chunk.

13. The system of claim 12 wherein at least one data structure comprises a bitmap, Bloom filter or Bloomier filter.

14. The system of claim 11 wherein the deduplication system includes a compression mechanism that compresses the chunk if the estimate of the compressibility of the chunk achieves a threshold value.

15. The system of claim 14 wherein the compression mechanism uses the estimate of the compressibility of the chunk at least in part as a hint to select a compression algorithm.

16. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising, estimating compressibility of a data block, including hashing at least some of the data of the data block into values in a data structure, using the data structure to obtain an estimated data entropy of the data block, and using the estimated data entropy to determine whether to compress the data block.

17. The one or more computer-readable media of claim 16 having further computer-executable instructions comprising, determining from the estimated data entropy that the data block is to be compressed, and compressing the data block.

18. The one or more computer-readable media of claim 17 having further computer-executable instructions comprising, using the estimated data entropy, and zero or more other estimated data entropies, as at least one factor in selecting a compression algorithm for compressing the data block.

19. The one or more computer-readable media of claim 16 wherein using the data structure to obtain an estimated data entropy of the data block comprises tracking distinct values in the data structure, and using a count of the distinct values relative as part of obtaining estimated data entropy.

20. The one or more computer-readable media of claim 16 having further computer-executable instructions comprising sampling data in the data block based upon a sliding window size parameter and a sampling parameter.