System and Methods For Accelerated Data Storage And Retrieval

• US 20110208833A1
• Filed: 05/05/2011
• Published: 08/25/2011
• Est. Priority Date: 03/11/1999
• Status: Active Grant

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J.
• Granted Patent: US 8,719,438 B2
• Time in Patent Office: Days
• US Class Current: 709/217
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 5/843 on film
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 5/907 using static stores, e.g. storage tubes or semiconductor memories H04N5/91 takes precedence
• CPC Class Codes: H04N 9/8042 involving data reduction
• CPC Class Codes: H04N 9/8227 the additional signal being at least another television signal

Abstract

Systems and methods for providing accelerated data storage and retrieval utilizing lossless data compression and decompression. A data storage accelerator includes one or a plurality of high speed data compression encoders that are configured to compress data. The compressed data is subsequently stored in a target memory or other storage device whose input data storage bandwidth is lower than the original input data stream bandwidth. Similarly, a data retrieval accelerator includes one or a plurality of high speed data decompression decoders that are configured to decompress data at a rate equivalent to or faster than the input data stream from the target memory or storage device. The decompressed data is then output at rate data that is greater than the output rate from the target memory or data storage device.

Claims

1. A computer-implemented method for accelerating data transmittal on an output to a data storage device, the output associated with an output bandwidth, comprising:

receiving a data stream in a received form, wherein the received data stream comprises a plurality of data blocks;

determining a compression ratio condition based, at least in part, on the output bandwidth;

determining a compression technique from a plurality of compression techniques, wherein the determined compression technique is able to compress a data block from the plurality of data blocks such that a compression ratio when the determined compression technique is applied to the data block in the received form meets the compression ratio condition;

compressing, using software, the data block using the compression technique to determine a compressed data block; and

transmitting, on the output to the data storage device, the compressed data block in an output data stream to the data storage device, the compressing and the transmitting together occurring more quickly than a length of time to transmit the data block on the output in the received form.

2. The method of claim 1, further comprising:

storing the plurality of data blocks in an input data buffer; and

counting a size of the plurality of input data blocks stored in the input data buffer,

wherein the determining the compression ratio condition comprises determining a compression ratio condition based, at least in part, on the counted size and the output bandwidth.

3. The method of claim 2, further comprising:

timing receipt of the plurality of data blocks; and

determining an input transmission rate of the data based, at least in part, on the counted size of the plurality of data blocks and an amount of time to receive the plurality of data blocks,

wherein the determining the compression ratio condition comprises determining the compression ratio condition based on a ratio of the determined input transmission rate to the output bandwidth,

wherein the determining the compression technique comprises determining the compression technique such that the determined compression technique is able to compress the data block to a compression ratio that does not exceed the ratio of the determined input transmission rate and the output bandwidth.

4. The method of claim 1, wherein the determining the compression technique comprises:

compressing the data block using a first compression technique in the plurality of compression techniques to determine a first compressed data block;

measuring a first compression ratio of the first compressed data block with respect to the data block in the received form;

compressing the data block using a second compression technique in the plurality of compression techniques to determine a second compressed data block;

measuring a second compression ratio of the second compressed data block with respect to the data block in the received form; and

selecting the first or the second compression technique depending, at least in part, on whether an associated compression ratio meets a compression ratio condition.

5. The method of claim 4, wherein the compressing the data block using the first compression technique and the compressing the data block using the second compression technique occur, at least in part, in parallel.

6. The method of claim 1, further comprising:

selecting, from a plurality of incoming data streams, the data stream.

7. The method of claim 6, wherein the plurality of incoming data streams includes at least one video data stream.

8. The method of claim 7, wherein the plurality of incoming data streams further includes at least one audio data stream.

9. The method of claim 1, wherein the receiving the data stream comprises receiving video data representing at least a portion of a digital video, and

wherein the determining the compression ratio condition comprises determining the compression ratio condition based, at least in part, on a resolution for a target device to display the video.

10. The method of claim 9, wherein the compressing includes using a lossy data compression technique to remove video data in excess of the target device display resolution.

11. The method of claim 10, wherein the receiving the data stream comprises receiving video data representing at least a portion of a digital video,

wherein the determining the compression ratio condition comprises determining the compression ratio condition based, at least in part, on a contrast ratio for a target device to display the video, and

wherein the compressing includes using a lossy data compression technique to remove video data in excess of the contrast ratio.

12. The method of claim 1, further comprising:

adjusting the compression ratio condition according to a change in the output bandwidth.

13. The method of claim 12, further comprising:

determining a second compression technique, different from the first compression technique, from the plurality of compression techniques, the second compression technique able to compress a second data block from the plurality of data blocks such that a compression ratio when the second compression technique is applied to the data block in the received form meets the adjusted compression ratio condition;

compressing the second data block using the second compression technique to determine a second compressed data block; and

transmitting, on the output to the data storage device, the second compressed data block in the compressed data stream to the data storage device, the compressing the second data block and the transmitting the second compressed data block together occurring more quickly than a length of time to transmit the second data block on the output in the received form.

14. The method of claim 1, wherein the compressing using software comprises providing program instructions stored in memory to a processor, the program instructions specifying how the processor executes the compression technique.

15. A system for accelerating data transmittal on an output of a data storage device, the output associated with an output bandwidth, comprising:

an input that receives a data stream in a received form, wherein the data stream comprises a plurality of data blocks;

a compression ratio module that (i) determines a compression ratio condition based, at least in part, on the output bandwidth and (ii) determines a compression technique from a plurality of compression techniques, wherein the determined compression technique is able to compress a data block from the plurality of data blocks such that a compression ratio when the compression technique is applied to the data block meets the compression ratio condition;

an encoder module that compresses the data block using the compression technique to determine a compressed data block; and

an interface to the output to the data storage device, wherein the interface transmits the compressed data block in an output data stream to the data storage device, a combined length of time for the encoder module to compress the data block and for the interface to transmit the data block being less than a length of time to transmit the data block on the output in the received form.

16. The system of claim 15, further comprising:

an input buffer that stores the plurality of data blocks; and

a counter module that counts a size of the plurality of data blocks stored in the input buffer,

wherein the compression ratio module determines the compression ratio condition based, at least in part, on the counted size and the output bandwidth.

17. The system of claim 15, wherein the counter module times receipt of the plurality of data blocks and determines an input transmission rate of the data based, at least in part, on the counted size of the plurality of data blocks and an amount of time to receive the plurality of data blocks,

wherein the compression ratio module (i) determines the compression ratio condition based on a ratio of the determined input transmission rate to the output bandwidth and (ii) determines the compression technique comprises determining the compression technique such that the determined compression technique is able to compress the data block to a compression ratio that does not exceed the ratio of the determined input transmission rate and the output bandwidth.

18. The system of claim 15, wherein the encoder module comprises:

a first encoder that compresses the data block using a first compression technique to determine a first compressed data block; and

a second encoder that compresses the data block using a second compression technique, different from the first compression technique to determine a first compressed data block, and wherein the system further comprises;

a first counter that measures a first compression ratio of the first compressed data block with respect to the data block in the received form; and

a second counter that measures a second compression ratio of the second compressed data block with respect to the data block in the received form,

wherein the compression ratio module selects the first or the second compression technique depending, at least in part, on whether an associated first or second compression ratio meets the determined compression ratio condition.

19. The system of claim 18, wherein the first and second encoders operate, at least in part, in parallel.

20. The system of claim 15, further comprising:

a multiplexer that receives a plurality of incoming data streams and selects, from the plurality of incoming data streams, the data stream received by the input at the input transmission rate.

21. The system of claim 20, wherein the plurality of incoming data streams includes at least one video data stream.

22. The system of claim 21, wherein the plurality of incoming data streams further includes at least one audio data stream.

23. The system of claim 15, wherein the data stream includes video data representing at least a portion of a digital video, and

wherein the compression ratio module determines the compression ratio condition based, at least in part, on a resolution for a target device to display the video.

24. The system of claim 23, wherein the encoder module uses a lossy data compression technique to remove video data in excess of the target device display resolution.

25. The system of claim 15, wherein the data stream includes video data representing at least a portion of a digital video,

wherein the compression ratio module determines the compression ratio condition based, at least in part, on a contrast ratio for a target device to display the video, and

wherein the encoder module uses a lossy data compression technique to remove video data in excess of the contrast ratio.

26. The system of claim 15, wherein the compression ratio module adjusts the compression ratio condition according to a change in the output bandwidth.

27. The system of claim 26, wherein the compression ratio module determines a second compression technique from the plurality of compression techniques, the second compression technique able to compress a second data block from the plurality of data blocks such that a compression ratio when the second compression technique is applied to the data block in the received form meets the adjusted compression ratio condition,

wherein the encoder module compresses the second data block using the second compression technique to determine a second compressed data block, and

wherein the interface transmits the second compressed data block in the compressed data stream to the data storage device, a combined length of time for the encoder module to compress the second data block and for the interface to transmit the second compressed data block being less than a length of time to transmit the data block on the output in the received form.

28. The system of claim 15, wherein the encoder module is implemented by providing program instructions stored in memory to a processor, the program instructions specifying how the processor executes the compression technique.

29. A computer program product, comprising at least one non-transitory computer readable storage medium, the at least one non-transitory computer readable storage medium having embodied thereon computer readable program code for accelerating data transmittal on an output to a data storage device, the output associated with an output bandwidth, the computer readable program code comprising:

a first computer readable program code for causing a computer to receive a data stream in a received form, wherein the received data stream comprises a plurality of data blocks;

a second computer readable program code for causing the computer to determine a compression ratio condition based, at least in part, on the output bandwidth;

a third computer readable program code for causing the computer to determine a compression technique from a plurality of compression techniques, wherein the determined compression technique is able to compress a data block from the plurality of data blocks such that a compression ratio when the determined compression technique is applied to the data block in the received form meets the compression ratio condition;

a fourth computer readable program code for causing the computer to compress the data block using the compression technique to determine a compressed data block; and

a fifth computer readable program code for causing the computer to transmit, on the output to the data storage device, the compressed data block in an output data stream to the data storage device, the compressing and the transmitting together occurring more quickly than a length of time to transmit the data block on the output in the received form.

30. A system for accelerating data transmittal on an output of a data storage device, the output associated with an output bandwidth, comprising:

an input capable of receiving a data stream in a received form, wherein the received data stream comprises a plurality of data blocks;

a compression ratio module capable of;

(i) determining a compression ratio condition based, at least in part, on the output bandwidth, and

(ii) determining a compression technique from a plurality of compression techniques, wherein the determined compression technique is able to compress a data block from the plurality of data blocks such that a compression ratio when the determined compression technique is applied to the data block in the received form meets the compression ratio condition;

an encoder module capable of compressing the data block using the compression technique to determine a compressed data block; and

an interface to the output to the data storage device, the interface capable of transmitting, on the output to the data storage device, the compressed data block in an output data stream to the data storage device, the compressing and the transmitting together occurring more quickly than a length of time to transmit the data block on the output in the received form.