Methods and apparatus for performing adaptive compression

• US 20070096954A1
• Filed: 10/03/2006
• Published: 05/03/2007
• Est. Priority Date: 10/27/2005
• Status: Active Grant

• Current Assignee: Carbonite LLC (Open Text Corporation)
• Original Assignee: Evault Incorporated (Seagate Technology Holdings Plc)
• Inventors: Boldt, Timothy, Lewitzky, Andre
• Granted Patent: US 7,460,032 B2
• Time in Patent Office: Days
• US Class Current: 341/50
• 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: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/156 Availability of hardware or computational resources, e.g. encoding based on power-saving criteria
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/164 Feedback from the receiver or from the transmission channel
• CPC Class Codes: H04N 19/169 characterised by the coding unit, i.e. the structural portion or semantic portion of the video signal being the object or the subject of the adaptive coding
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock

Abstract

Methods and apparatus for performing adaptive compression are disclosed. A data stream is divided into a plurality of data segments. When one of the plurality of data segments is compressed, it is determined whether the compression has been successful. When the compression has been successful, a data segment in proximity to the compressed segment (e.g., the next data segment in the plurality of data segments) is compressed. However, when the compression has been unsuccessful, one or more of the plurality of data segments are skipped (i.e., not compressed) before compression is attempted on another one of the plurality of data segments. When a data segment is compressed, the compression algorithm (and any associated parameter(s)) that is applied is selected based upon a variety of factors, such as the length of the data segment, CPU speed, CPU availability, and/or data throughput such as the network bandwidth or network availability (e.g., where data is to be transmitted via a network interface). The compression algorithm (and any associated parameter(s)) may also be selected, at least in part, based upon a set of user preferences that indicate a preference between the speed with which compression is performed and the amount that a data segment is compressed.

Claims

1. A method of compressing a file including a plurality of data segments, comprising:

dividing the file into a plurality of segments of data;

compressing one of the plurality of segments of data;

determining whether compression of the one of the plurality of segments of data was successful; and

when the compression of the one of the plurality of segments of data was not successful, skipping one or more of the plurality of segments of data in proximity to the one of the plurality of segments of data that has been unsuccessfully compressed before applying the compressing step to another one of the plurality of segments of data.

2. The method as recited in claim 1, wherein the one or more of the plurality of segments of data are in proximity to the one of the plurality of segments of data that has been unsuccessfully compressed when the one or more of the plurality of segments of data are within a specified number of data segments of the segment of data that has been unsuccessfully compressed.

3. A method of compressing a data stream, comprising:

dividing the data stream into a plurality of segments of data;

compressing one of the plurality of segments of data;

determining whether compression of the one of the plurality of segments of data was successful; and

when the compression of the one of the plurality of segments of data was not successful, skipping one or more of the plurality of segments of data following the one of the plurality of segments of data that has been unsuccessfully compressed before applying the compressing step to another one of the plurality of segments of data.

4. The method as recited in claim 3, wherein the plurality of segments of data are variable length data segments.

5. The method as recited in claim 3, further comprising:

when the compression of the one of the plurality of segments of data was successful, compressing a next one of the plurality of segments of data following the one of the plurality of segments of data that has been compressed.

6. The method as recited in claim 3, further comprising:

tracking a number of the plurality of segments of data (n) that have not compressed successfully;

wherein skipping one or more of the plurality of segments of data includes skipping (n*2) of the plurality of segments of data before compressing another one of the plurality of segments of data.

7. The method as recited in claim 6, wherein the number of the plurality of segments of data (n) that have not compressed successfully is a number of consecutive segments of data that have not compressed successfully.

8. The method as recited in claim 3, further comprising:

tracking a number of the plurality of segments of data (n) that have not compressed successfully;

wherein skipping one or more of the plurality of segments of data includes skipping one of the plurality of segments of data when n is equal to one and skipping 2(n−

1) of the plurality of segments of data when n is greater than one.

9. The method as recited in claim 8, wherein the number of the plurality of segments of data (n) that have not compressed successfully is a number of consecutive segments of data that have not compressed successfully.

10. The method as recited in claim 3, further comprising:

identifying a desired compression amount; and

determining an amount that the data segment has been compressed;

wherein determining whether compression of the one of the plurality of data segments was successful includes comparing the desired compression amount with the amount that the data segment has been compressed.

11. The method as recited in claim 10, wherein compression of the one of the plurality of data segments was successful when the amount that the one or more data segments has been compressed is greater than or equal to the desired compression amount.

12. The method as recited in claim 10, wherein identifying a desired compression amount comprises:

identifying a desired compression amount based upon at least one of data throughput, network bandwidth, network availability, CPU availability, and CPU speed.

13. The method as recited in claim 10, wherein identifying a desired compression amount comprises:

identifying a desired compression amount based upon a set of user specified preferences.

14. The method as recited in claim 13, wherein the desired compression amount is associated with at least one of data throughput, network bandwidth, network availability, CPU availability, and CPU speed.

15. The method as recited in claim 5, further comprising:

identifying a type of compression to apply;

wherein compressing a next one of the plurality of segments of data following the one of the plurality of segments of data that has been compressed includes applying the identified type of compression to the next one of the plurality of segments of data following the one of the plurality of segments of data that has been compressed.

16. The method as recited in claim 15, wherein identifying the type of compression to apply comprises:

applying a plurality of types of compression to one or more of the plurality of data segments;

determining a result of the applying the plurality of types of compression to the one or more of the plurality of data segments; and

selecting one of the plurality of types of compression based upon the result of the applying the plurality of types of compression to the one or ore of the plurality of data segments.

17. The method as recited in claim 15, wherein the type of compression is associated with a set of user preferences.

18. The method as recited in claim 17, wherein the set of user preferences indicates at least one of a desired speed of compression, a desired compression amount, and an indication of the importance of the speed of compression with respect to the importance of the amount of compression.

19. The method as recited in claim 15, wherein the type of compression is an identified compression algorithm or indicates that no compression is to be performed.

20. The method as recited in claim 19, wherein the type of compression further includes one or more parameters associated with the identified compression algorithm.

21. The method as recited in claim 15, further comprising:

determining at least one of a length of the data segment that has been compressed, data throughput, network bandwidth, network availability, CPU availability, and CPU speed;

wherein identifying a type of compression to apply is performed based upon at least one of the length of the data segment that has been compressed, data throughput, network bandwidth, network availability, CPU availability, and CPU speed.

22. The method as recited in claim 21, wherein determining the network availability is performed when the data is to be transmitted via a network interface for storage at a remotely located storage medium.

23. The method as recited in claim 21, wherein the type of compression is an identified compression algorithm or indicates that no compression is to be performed.

24. The method as recited in claim 23, wherein the type of compression further includes one or more parameters associated with the identified compression algorithm.

25. The method as recited in claim 21, wherein the type of compression is further associated with a set of user preferences.

26. The method as recited in claim 25, wherein the set of user preferences indicates at least one of a desired speed of compression, a desired compression amount, and an indication of the importance of the speed of compression with respect to the importance of the amount of compression.

27. The method as recited in claim 26, wherein identifying a type of compression to apply comprises:

obtaining a set of information associated with the set of user preferences; and

identifying the type of compression associated with the at least one of the length of the data segment that has been compressed, data throughput, network bandwidth, network availability, CPU availability, and CPU speed from the set of information.

28. The method as recited in claim 25, wherein identifying a type of compression to apply comprises:

obtaining a set of information associated with the set of user preferences; and

identifying the type of compression associated with the at least one of the length of the data segment that has been compressed, data throughput, network bandwidth, network availability, CPU availability, and CPU speed from the set of information.

29. The method as recited in claim 28, further comprising:

identifying a desired compression amount from the set of information;

determining an amount that the data segment has been compressed;

wherein determining whether compression of the one of the plurality of data segments was successful includes comparing the desired compression amount with the amount that the data segment has been compressed.

30. The method as recited in claim 21, wherein determining the network availability comprises:

identifying a queue of data buffers to be written to the remotely located storage medium; and

ascertaining an availability of the data buffers.

31. The method as recited in claim 30, further comprising:

comparing the availability of the data buffers with a desired availability.

32. The method as recited in claim 21, wherein determining the network availability comprises:

identifying a queue of data buffers to be written to the remotely located storage medium;

determining a processing time associated with applying the type of compression to one or more data segments; and

ascertaining a total amount of time waiting for the queue to store the one or more data segments in the queue.

33. The method as recited in claim 32, further comprising:

calculating an efficiency of compression equal to the processing time divided by the total amount of time waiting for the queue.

34. A method of identifying a type of compression to apply to one or more data segments of a data stream, comprising:

determining at least one of data throughput, network bandwidth, network availability, CPU availability, and CPU speed;

identifying a type of compression to apply to one or more data segments of the data stream based upon at least one of the data throughput, network bandwidth, network availability, CPU availability, and CPU speed; and

applying the type of compression to one or more data segments of the data stream.

35. The method as recited in claim 34, wherein determining the network availability is performed when the data is to be transmitted via a network interface for storage at a remotely located storage medium.

36. The method as recited in claim 34, wherein the type of compression is an identified compression algorithm or indicates that no compression is to be performed.

37. The method as recited in claim 36, wherein the type of compression further includes one or more parameters associated with the identified compression algorithm.

38. The method as recited in claim 34, wherein the type of compression is further associated with a set of user preferences.

39. The method as recited in claim 38, wherein the set of user preferences indicates at least one of a desired speed of compression, a desired compression amount, and an indication of the importance of the speed of compression with respect to the importance of the amount of compression.

40. The method as recited in claim 39, wherein identifying a type of compression to apply comprises:

obtaining a set of information associated with the set of user preferences; and

identifying the type of compression associated with the at least one of a length of the data segments to be compressed, the data throughput, network bandwidth, network availability, CPU availability, and CPU speed from the set of information.

41. The method as recited in claim 34, further comprising:

ascertaining a desired compression amount;

determining an amount that the one or more data segments has been compressed; and

comparing the desired compression amount with the amount that the one or more data segments has been compressed;

determining whether to compress one or more data segments following the one or more data segments that have been compressed based upon the comparison.

42. The method as recited in claim 41, further comprising:

when the amount that the one or more data segments has been compressed is greater than the desired compression amount, compressing one or more data segments following the one or more data segments that have been compressed; and

when the amount that the one or more data segments has been compressed is not greater than the desired compression amount, skipping compression of one or more data segments following the one or more data segments that have been compressed.

43. The method as recited in claim 41, wherein ascertaining a desired compression amount comprises:

identifying a desired compression amount based upon at least one of the data throughput, network bandwidth, network availability, CPU availability, and CPU speed.

44. The method as recited in claim 41, wherein ascertaining a desired compression amount comprises:

identifying a desired compression amount based upon a set of user specified preferences.

45. The method as recited in claim 34, wherein determining the network availability comprises:

identifying a queue of data buffers to be written to the remotely located storage medium; and

ascertaining an availability of the data buffers.

46. The method as recited in claim 45, further comprising:

comparing the availability of the data buffers with a desired availability.

47. The method as recited in claim 34, wherein determining the network availability comprises:

identifying a queue of data buffers to be written to the remotely located storage medium;

determining a processing time associated with applying the type of compression to one or more data segments; and

ascertaining a total amount of time waiting for the queue to store the one or more data segments in the queue.

48. The method as recited in claim 47, further comprising:

calculating an efficiency of the compression equal to the processing time divided by the total amount of time waiting for the queue.

49. An apparatus for compressing a file including a plurality of data segments, comprising:

a processor; and

a memory, at least one of the processor or the memory being adapted for;

dividing the file into a plurality of segments of data;

compressing one of the plurality of segments of data;

determining whether compression of the one of the plurality of segments of data was successful; and

when the compression of the one of the plurality of segments of data was not successful, skipping one or more of the plurality of segments of data in proximity to the one of the plurality of segments of data that has been unsuccessfully compressed before applying the compressing step to another one of the plurality of segments of data.

50. A computer-readable medium storing thereon computer-readable instructions for compressing a file including a plurality of data segments, comprising:

instructions for dividing the file into a plurality of segments of data;

instructions for compressing one of the plurality of segments of data;

instructions for determining whether compression of the one of the plurality of segments of data was successful; and

instructions for skipping one or more of the plurality of segments of data in proximity to the one of the plurality of segments of data that has been unsuccessfully compressed before applying the compressing step to another one of the plurality of segments of data when the compression of the one of the plurality of segments of data was not successful.