SYSTEM AND METHODS FOR ACCELERATED DATA STORAGE AND RETRIEVAL

• US 20100318684A1
• Filed: 01/20/2010
• Published: 12/16/2010
• Est. Priority Date: 03/11/1999
• Status: Abandoned Application

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J.
• Application Number:
  US12/690,125
• Publication Number:
  US 20100318684A1
• Time in Patent Office: Days
• US Class Current: 709/247
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: G11B 20/00007 Time or data compression or expansion audio compression based on psychoacoustics G10L19/00; data processing for reproducing audio data at different playback speeds G10L21/04; video compression H04N19/00; data compression per se H03M7/30
• CPC Class Codes: G11B 20/10 Digital recording or reproducing
• CPC Class Codes: G11B 2020/00079 the compression ratio or quality level being adapted to circumstances, e.g. to the available recording space
• CPC Class Codes: G11B 2020/10759 content data
• 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/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 21/231 Content storage operation, e.g. caching movies for short term storage, replicating data over plural servers, prioritizing data for deletion
• CPC Class Codes: H04N 21/232 Content retrieval operation locally within server, e.g. reading video streams from disk arrays storage management G06F3/0604; details of querying and searching of video data from a database G06F16/739
• CPC Class Codes: H04N 21/42661 for reading from or writing on a magnetic storage medium, e.g. hard disk drive
• CPC Class Codes: H04N 21/4325 : by playing back content from the storage medium reproduction of recorded television signals H04N5/76; reproduction of recorded television signals H04N9/79
• CPC Class Codes: H04N 21/4334 : Recording operations recording of a television signal H04N5/76; arrangements for recording or accumulating broadcast information or broadcast-related information H04H60/27
• 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 and/or lossy 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 or lossy 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 or lossy 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-30. -30. (canceled)

31. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for providing accelerated data storage, said method comprising:

receiving a digital data stream at an input data transmission rate which is greater than a data storage rate of a target storage device, the digital data stream comprising a plurality of data blocks;

compressing the plurality of data blocks with a number of encoders to provide a plurality of compressed data blocks;

determining a compression ratio associated with each of the plurality of compressed data blocks and selecting, based, at least in part, on the determined compression ratios, at least one of the compressed data blocks to provide as a compressed digital data stream; and

storing the compressed digital data stream in the target storage device at a compression rate, wherein the combined length of time required for performing said compressing and said storing the compressed digital data stream in the target storage device is less than a length of time required for storing the digital data stream in the target storage device.

32. The program storage device of claim 31, wherein the compression rate is at least equal to the ratio of the input data transmission rate to the data storage rate so as to provide continuous storage of the input digital data stream at the input data transmission rate.

33. The program storage device of claim 31, wherein the instructions for compressing comprise instructions for performing lossy data compression.

34. The program storage device of claim 31, wherein the instructions for compressing comprise instructions for performing lossless and lossy data compression.

35. The program storage device of claim 31, wherein the instructions for compressing comprise instructions for:

reading a first parameter that is indicative of a compression type to be applied to the input digital data stream; and

selecting at least one allowable encoder based on the first parameter.

36. The program storage device of claim 35, wherein the compression type is one of lossless data compression, lossy data compression, and a combination thereof.

37. The program storage device of claim 35, wherein each data block in the plurality has a first parameter associated therewith indicative of a compression type to be applied to the data block.

38. The program storage device of claim 35, further comprising instructions for reading a second data parameter that is indicative of an amount of information loss that is permissible, if lossy data compression is selected.

39. The program storage device of claim 38, wherein the first and second data parameters are located within a header of a data block.

40. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method for providing accelerated retrieval of stored data, said method comprising:

retrieving a compressed digital data stream from a target storage device at a rate equal to a data access rate of the target storage device;

reading, from the compressed digital data stream, a first parameter that is indicative of a decompression type to be applied to the compressed digital data stream;

selecting a subset of decoders from a plurality of decoders based, at least in part, on the first parameter, and enabling the selected subset of decoders; and

decompressing the compressed digital data stream, using the enabled subset of decoders, at a decompression rate to produce decompressed data, wherein the combined length of time required for performing said retrieving the compressed digital data stream from the target storage device and said decompressing the compressed digital data stream is less than a length of time required for retrieving the decompressed data from the target storage device.

41. The program storage device of claim 40, wherein the instructions for decompressing comprise instructions for performing lossy data decompression.

42. The program storage device of claim 40, wherein the instructions for decompressing comprise instructions for performing a combination of lossless and lossy data decompression.

44. The program storage device of claim 40, wherein the decompression type is one of lossless and lossy data decompression.

45. The program storage device of claim 40, further comprising instructions for reading a second parameter that is indicative of an amount of information loss that is permissible, if lossy data decompression is selected.

43. (canceled)

46. A method for providing accelerated data storage comprising:

receiving a digital data stream at an input data transmission rate which is greater than a data storage rate of a target storage device, the digital data stream comprising a plurality of data blocks;

compressing the plurality of data blocks with a number of encoders to provide a plurality of compressed data blocks;

determining a compression ratio associated with each of the compressed data blocks and selecting, based, at least in part, on the determined compression ratios, at least one of the compressed data blocks to provide as a compressed digital data stream; and

storing the compressed digital data stream in the target storage device at a compression rate, wherein the combined length of time required for performing said compressing and said storing the compressed digital data stream in the target storage device is less than a length of time required for storing the digital data stream in the target storage device.

47. The method of claim 46, wherein the compression rate is at least equal to the ratio of the input data transmission rate to the data storage rate so as to provide continuous storage of the input digital data stream at the input data transmission rate.

48. The method of claim 46, wherein the compressing is performed using lossy data compression.

49. The method of claim 46, wherein the compressing is performed using lossless and lossy data compression.

50. The method of claim 46, wherein the compressing comprises:

reading a first parameter that is indicative of a compression type to be applied to the input digital data stream; and

selecting at least one allowable encoder based on the first parameter.

51. A method for providing accelerated data storage comprising:

receiving a digital data stream at an input data transmission rate which is greater than a data storage rate of a target storage device, the digital data stream comprising a plurality of data blocks;

losslessly compressing the the plurality of data blocks with a number of encoders to provide a plurality of compressed data blocks;

determining a compression ratio associated with each of the plurality of compressed data blocks and selecting, based, at least in part, on the determined compression ratios, at least one of the compressed data blocks to provide as a compressed digital data stream; and

storing the compressed digital data stream in the target storage device at a compression rate, wherein the combined length of time required for performing said losslessly compressing and said storing the compressed digital data stream in the target storage device is less than a length of time required for storing the digital data stream in the target storage device.

52. The method of claim 51, further comprising:

reading a first parameter that is indicative of a decompression type to be applied to the compressed digital data stream; and

selecting at least one allowable decoder based on the first parameter.

53. A method for providing accelerated retrieval of stored data comprising:

retrieving a compressed digital data stream from a target storage device at a rate equal to a data access rate of the target storage device

reading, from the compressed digital data stream, a first parameter that is indicative of a decompression type to be applied to the compressed digital data stream;

selecting a subset of decoders from a plurality of decoders based, at least in part, on the first parameter, and enabling the selected subset of decoders; and

decompressing the compressed digital data stream, using the enabled subset of decoders, at a decompression rate to produce decompressed data, wherein the combined length of time required for performing said retrieving the compressed digital data stream from the target storage device and said decompressing the compressed digital data stream is less than a length of time required for retrieving the decompressed data from the target storage device.

54. The method of claim 53, wherein the decompressing comprises performing lossy data decompression.

55. The method of claim 53, wherein the decompressing comprises performing a combination of lossless and lossy data decompression.

57. The method of claim 53, wherein the decompression type is one of lossless and lossy data decompression.

58. The method of claim 53, further comprising reading a second parameter that is indicative of an amount of information loss that is permissible, if lossy data decompression is selected.

56. (canceled)