System and methods for accelerated data storage and retrieval

• US 8,504,710 B2
• Filed: 10/26/2006
• Issued: 08/06/2013
• 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:
  US11/553,427
• Publication Number:
  US 20070050515A1
• Time in Patent Office: 2,476 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 simultaneously or sequentially losslessly compress data at a rate equivalent to or faster than the transmission rate of an input data stream. 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 simultaneously or sequentially losslessly 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. The data storage and retrieval accelerator method and system may employed: in a disk storage adapter to reduce the time required to store and retrieve data from computer to disk; in conjunction with random access memory to reduce the time required to store and retrieve data from random access memory; in a display controller to reduce the time required to send display data to the display controller or processor; and/or in an input/output controller to reduce the time required to store, retrieve, or transmit data.

Claims

1. A system comprising:

a device;

a data storage accelerator, able to communicate with said device, that;

(i) receives a data stream, including a first block and a second block, in received form,

(ii) compresses each of said first and second data blocks with a first compression technique and a second compression technique different from said first compression technique to output a first compressed data block for the first data block compressed with the first compression technique, a second compressed data block for the first data block compressed with the second compression technique, a third compressed data block compressed with the second data block and the first compression technique, and a fourth compressed data block compressed with the second data block and the second compression technique,

(iii) measures compression ratios associated with the compressed first, second, third, and fourth data blocks,

(iv) selects the compressed first data block or the compressed second data block for a compressed data stream based, at least in part, on associated measured compression ratios,

(v) selects the compressed third data block or the compressed fourth data block for the compressed data stream based, at least in part, on associated measured compression ratios, and

(vi) provides the selected compressed data stream to said device, and

wherein a combined length of time required for said data stream to be compressed by said data storage accelerator and for providing said compressed data stream to said device using said data storage accelerator is less than a length of time required for providing said data stream, in said received form, to said device; and

a description module configured to append a first descriptor indicative of said first compression technique, and a second descriptor indicative of said second compression technique, to said compressed data stream.

2. The system of claim 1, wherein said first compression technique includes compressing with Huffman encoding.

3. The system of claim 1, wherein said first compression technique includes compressing with Lempel-Ziv encoding.

4. The system of claim 1, wherein said first compression technique includes compressing said first data block with a plurality of encoders applied in a sequential order to said first data block.

5. The system of claim 1, wherein said first compression technique includes compressing with a plurality of encoders in a parallel configuration.

6. The system of claim 1, wherein said first compression technique includes compressing with a plurality of encoders in a parallel configuration and each one of said plurality of encoders is an identical type of encoder.

7. The system of claim 1, wherein said first compression technique comprises compressing with a first encoder.

8. The system of claim 1, wherein said data stream comprises a collection of multiple files.

9. The system of claim 1, wherein said data stream includes a third data block and a fourth data block.

10. The system of claim 1, wherein said data stream includes a third data block and a fourth data block and said compressed data stream is provided by compressing said third data block with a third compression technique and compressing said fourth data block with a fourth compression technique.

11. The system of claim 1, wherein the portion of the compressed data stream associated with said first data block is decompressed with a decompression technique associated with said first descriptor.

12. The system of claim 1, wherein said first descriptor is utilized to select a decompression technique to decompress the portion of said compressed data stream associated with said first data block.

13. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block and said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block.

14. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block, said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block, and said first compression technique includes compression with a plurality of encoders.

15. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block, said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block, and said first compression technique includes compression with a plurality of encoders in a parallel configuration.

16. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block, said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block, and said first compression technique includes compression of said first data block by applying a plurality of encoders in a sequential order to said first data block.

17. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block, said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block, said first compression technique includes compression with a plurality of encoders, and said data stream includes a plurality of files.

18. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block, said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block, said first compression technique includes compression with a plurality of encoders, and said compressed data stream includes video data.

19. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block, said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block, said first compression technique includes compression with a plurality of encoders, and said compressed data stream includes digital video data.

20. The system of claim 1, wherein said first descriptor is utilized to select a first decompression technique to decompress the portion of said compressed data stream associated with said first data block, said second descriptor is utilized to select a second decompression technique to decompress the portion of said compressed data stream associated with said second data block, said first compression technique includes compression with a plurality of encoders, said compressed data stream includes video data, and said device is a magnetic storage device.

21. The system of claim 1, further comprising:

a multiplexer that receives a plurality of input data streams and selects the data stream for receipt at the data storage accelerator.

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

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

24. The system of claim 1, wherein the data stream received at the data storage accelerator comprises video data for a video, and wherein at least one of the first and second compression techniques includes using a lossy data compression to remove video data in excess of a desired display resolution of a target device to display the video.

25. The system of claim 1, wherein the data storage accelerator is implemented in software.