System and methods for accelerated data storage and retrieval

• US 8,719,438 B2
• Filed: 05/05/2011
• Issued: 05/06/2014
• Est. Priority Date: 03/11/1999
• Status: Expired due to Fees

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J.
• Primary Examiner(s): Tran, Philip B
• Application Number:
  US13/101,994
• Publication Number:
  US 20110208833A1
• Time in Patent Office: 1,097 Days
• Field of Search: 709/231, 709/233, 709/247
• US Class Current: 709/231
• 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 an input data transmission rate of the data stream based on an amount of data received during a period of time;

determining a compression ratio parameter based, at least in part, on the determined input data transmission rate and the output bandwidth;

selecting a compression technique from a plurality of compression techniques such that a compression ratio when the determined compression technique is applied to a data block from the plurality of data blocks in the received form satisfies the determined compression ratio parameter;

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

wherein the determining the input data transmission rate comprises counting a size of the plurality of input data blocks stored in the input data buffer,

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

3. The method of claim 2, wherein the determining the input data transmission rate comprises:

timing receipt of the plurality of data blocks; and

determining the 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 parameter comprises determining the compression ratio parameter 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 foam; and

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

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 parameter comprises determining the compression ratio parameter 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 parameter comprises determining the compression ratio parameter 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 parameter 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 parameter;

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, at an input transmission rate, a data stream in a received form, wherein the data stream comprises a plurality of data blocks;

a counter module that determines an input transmission rate of the data stream based on an amount of data received during a period of time;

a compression ratio module that (i) determines a compression ratio parameter based, at least in part, on the input transmission rate determined by the counter module and the output bandwidth and (ii) selects a compression technique from a plurality of compression techniques such that a compression ratio when a compression technique is applied to the data block satisfies the determined compression ratio parameter;

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 to determine the amount of data received,

wherein the compression ratio module determines the compression ratio parameter 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 the 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 parameter 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 parameter.

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 parameter 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 parameter 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 parameter 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 parameter,

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 non-transitory computer readable storage medium having embodied thereon machine executable program code for accelerating data transmittal on an output to a data storage device, the output associated with an output bandwidth, the machine executable program code comprising:

a first machine executable program code for causing a computer to receive, at an input transmission rate, a data stream in a received form, wherein the received data stream comprises a plurality of data blocks;

a second machine executable program code for causing a computer to determine an input transmission rate of the data stream based on an amount of data received during a period of time;

a third machine executable program code for causing the computer to determine a compression ratio parameter based, at least in part, on the input transmission rate and the output bandwidth;

a fourth machine executable program code for causing the computer to select a compression technique from a plurality of compression techniques such that a compression ratio when the determined compression technique is applied to a data block in the received form satisfies the determined compression ratio parameter;

a fifth machine executable program code for causing the computer to compress the data block using the compression technique to determine a compressed data block; and

a sixth machine executable 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, at an input transmission rate, a data stream in a received form, wherein the received data stream comprises a plurality of data blocks;

a counter module capable, of determining'"'"' an input transmission rate of the data stream based on an amount of data received during a period of time;

a compression ratio module capable of;

(i) determining a compression ratio parameter based, at least in part, on the determined input transmission rate and the output bandwidth, and

(ii) selecting a compression technique from a plurality of compression techniques such that a compression ratio when the determined compression technique is applied to a data block in the received form satisfies the determined compression ratio parameter;

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.