US5313604A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for locating compressed data in a computed memory back up device including steps of refining estimater location
Assignee: HP Inc
•
Filing: 1990-11-13
•
Granted: 1994-05-17
•
Expires: 2010-11-13
Abstract
Abstract A method for utilizing computer memory devices when they have compressed data is disclosed. Specifically, the techniques focus on the field of operating devices so as to access randomly specified portions of such compressed data. It has particular applicability in computer tape drives such as are used in computer peripheral memory backup devices. These improved methods act to efficiently ascertain the location of the desired data with a minimum amount of effort. One embodiment of the present invention comprises the use of records which represent a number of files or an amount of data stored. Each record is independently compressed to allow independent access and uncompression. The records may include labels for identification purposes. Each label is typically an uncompressed value or series of values stored at the front of each record. Additionally, offsets are specified in labels to indicate the distance from the beginning of the first record to any item of data. The essence of the present invention is to simply calculate an estimated location utilizing an initial compression rate estimate, that is a percentage or ratio that represents the relationship between the average cumulative file size in compressed form of the same data in uncompressed form. Testing this estimate and subsequently refining it serves to efficiently search and retrieve the desired data.
Inventors
- 👤 Kurt E. Godwin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 21:04
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G11; G11B; G11B20/00; G11B20/00007; G11B27/00; G11B27/10; G11B27/102; G11B27/107; G11B27/19; G11B27/28; G11B27/30; G11B27/3027; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0682; G11B2220/00; G11B2220/90
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
89 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor, wherein such data has an identification index based upon uncompressed data, comprising the steps of: a. designating a desired data; then b. calculating an estimated location of said data within said memory media through use of said identification index based upon uncompressed data by applying a compression ratio; then c. reading said media at the estimated location; then d. locating said desired data through operation of said programmable data processor.
Claim 2
Independent Claim
89 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor, wherein such data has an identification index based upon uncompressed data, comprising the steps of: a. designating a desired data; then b. calculating an estimated location of said data within said memory media through use of said identification index based upon uncompressed data by applying a compression ratio; then c. reading said media at the estimated location; then d. locating said desired data through operation of said programmable data processor.
Claim 3
Dependent Claim
42 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 1 and further comprising the step of refining said estimated location after accomplishing said step of reading said media.
Claim 4
Dependent Claim
54 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 2 wherein said media is divided into records each having an identification label associated therewith and wherein said step of reading said media comprises the step of reading said identification label.
Claim 5
Dependent Claim
42 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 3 wherein said label comprises information indicating the amount of data existing in all prior records in uncompressed form.
Claim 6
Dependent Claim
71 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 4 wherein said step of calculating an estimated location of said data within said memory media comprises the step of applying a compression rate estimate to the amount of data existing in all prior records in uncompressed form as indicated by said label to obtain said compression ratio.
Claim 7
Dependent Claim
49 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 5 wherein said step of applying a compression rate estimate comprises the step of generating an estimated amount of compressed data prior to said desired data.
Claim 8
Dependent Claim
48 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 6 wherein said step of refining said estimated location comprises the step of testing said compression rate estimate through operation of the programmable data processor.
Claim 9
Dependent Claim
77 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 7 wherein said step of refining said estimated location further comprises the steps of: a. changing said compression rate estimate after accomplishing said step of testing said compression rate estimate; and then b. reconducting said step of calculating an estimated location of said data within said memory media with said changed compression rate estimate.
Claim 10
Dependent Claim
63 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 2 wherein said step of calculating an estimated location of said data within said memory media comprises the step of summing the total amount of data existing prior to the desired data to arrive at an uncompressed prior data sum.
Claim 11
Dependent Claim
44 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 3 wherein said label consists of information indicating the total amount of data existing in all prior records in uncompressed form.
Claim 12
Dependent Claim
63 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 10 wherein said step of calculating an estimated location of said data within said memory media comprises the step of summing the total amount of data existing prior to the desired data to arrive at an uncompressed prior data sum.
Claim 13
Dependent Claim
67 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 5 wherein said step of refining said estimated location further comprises the steps of: a. changing said compression rate estimate; and then b. reconducting said step of calculating an estimated location of said data within said memory media with said changed compression rate estimate.
Claim 14
Dependent Claim
48 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 5 wherein said step of refining said estimated location comprises the step of testing said compression rate estimate through operation of the programmable data processor.
Claim 15
Dependent Claim
77 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 13 wherein said step of refining said estimated location further comprises the steps of: a. changing said compression rate estimate after accomplishing said step of testing said compression rate estimate; and then b. reconducting said step of calculating an estimated location of said data within said memory media with said changed compression rate estimate.
Claim 16
Dependent Claim
102 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 13 wherein said step of testing said compression rate estimate further comprises the step of assuring that said amount of data existing in all prior records in uncompressed form as indicated by said label is less than that indicated by said uncompressed prior data sum after accomplishing said step of generating a difference between the amount of data existing in all prior records in uncompressed form indicated by said label and that indicated by said uncompressed prior data sum.
Claim 17
Dependent Claim
79 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 15 wherein said step of refining said estimated location further comprises the step of comparing said difference to a set acceptable error after accomplishing said step of generating said difference between the amount of data existing in all prior records in uncompressed form indicated by said label and that indicated by said uncompressed prior data sum.
Claim 18
Dependent Claim
46 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 16 wherein said method takes time to access the data and wherein said set acceptable error is set to optimize said access time.
Claim 19
Dependent Claim
53 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 16 wherein said step of locating said data comprises the steps of: a. uncompressing said record located; then b. accessing the desired data at an access point within said record.
Claim 20
Dependent Claim
73 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 18 wherein said step of locating said data further comprises the step of advancing said access point by an amount equal to said difference between the amount of data existing in all prior records in uncompressed form indicated by said label and that indicated by said uncompressed prior data sum.
Claim 21
Dependent Claim
46 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 7 wherein said step of testing said compression rate estimate comprises the step of comparing said label to said uncompressed prior data sum.
Claim 22
Dependent Claim
74 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 20 wherein said step of refining said estimated location further comprises the step of changing said compression rate estimate and reconducting said step of calculating an estimated location of said data within said memory media with said changed compression rate estimate after accomplishing said step of testing said compression rate estimate.
Claim 23
Dependent Claim
63 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 1 wherein said step of calculating an estimated location of said data within said memory media comprises the step of summing the total amount of data existing prior to the desired data to arrive at an uncompressed prior data sum.
Claim 24
Dependent Claim
60 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 22 wherein said step of calculating an estimated location of said data within said memory media further comprises the step of applying a compression rate estimate to said uncompressed prior data sum to obtain said compression ratio.
Claim 25
Dependent Claim
49 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 23 wherein said step of applying a compression rate estimate comprises the step of generating an estimated amount of compressed data prior to said desired data.
Claim 26
Dependent Claim
48 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 24 wherein said step of refining said estimated location comprises the step of testing said compression rate estimate through operation of the programmable data processor.
Claim 27
Dependent Claim
77 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 25 wherein said step of refining said estimated location further comprises the steps of: a. changing said compression rate estimate after accomplishing said step of testing said compression rate estimate; and then b. reconducting said step of calculating an estimated location of said data within said memory media with said changed compression rate estimate.
Claim 28
Dependent Claim
46 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 24 wherein said step of testing said compression rate estimate comprises the step of comparing said label to said uncompressed prior data sum.
Claim 29
Dependent Claim
74 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 27 wherein said step of refining said estimated location further comprises the step of changing said compression rate estimate and reconducting said step of calculating an estimated location of said data within said memory media with said changed compression rate estimate after accomplishing said step of testing said compression rate estimate.
Claim 30
Dependent Claim
70 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 28 wherein said step of comparing said label to said uncompressed prior data sum comprises the step of generating a difference between the amount of data existing in all prior records in uncompressed form indicated by said label and that indicated by said uncompressed prior data sum.
Claim 31
Dependent Claim
70 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 27 wherein said step of comparing said label to said uncompressed prior data sum comprises the step of generating a difference between the amount of data existing in all prior records in uncompressed form indicated by said label and that indicated by said uncompressed prior data sum.
Claim 32
Dependent Claim
82 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 27 wherein said step of testing said compression rate estimate further comprises the step of assuring that said amount of data existing in all prior records in uncompressed form as indicated by said label is less than that indicated by said uncompressed prior data sum after accomplishing said step of comparing said label to said uncompressed prior data sum.
Claim 33
Dependent Claim
46 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 25 wherein said step of testing said compression rate estimate comprises the step of comparing said label to said uncompressed prior data sum.
Claim 34
Dependent Claim
74 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 32 wherein said step of refining said estimated location further comprises the step of changing said compression rate estimate and reconducting said step of calculating an estimated location of said data within said memory media with said changed compression rate estimate after accomplishing said step of testing said compression rate estimate.
Claim 35
Independent Claim
48 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claims 5, 23, 26, 33 or 17 wherein the first compression rate utilized is the initial compression estimate and wherein said initial compression estimate is 50%.
Claim 36
Independent Claim
80 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claims 5, 23, 26, 33, or 17 wherein said method is accomplished repetitively for a plurality of searches and wherein said method further comprises the step of storing the last compression rate estimate after accomplishing said step of locating said data and wherein the compression rate estimate first utilized in the next search is said stored compression rate.
Claim 37
Independent Claim
66 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claims 5, 23, 26, 33 or 17 wherein said data is compressed through use of a compression technique, wherein the first compression rate utilized is the initial compression estimate and wherein said initial compression estimate is the average compression rate for that compression technique.
Claim 38
Dependent Claim
73 words
A method of accessing data stored in compressed form in a memory media associated with a programmable data processor as described in claim 36 wherein said method is accomplished repetitively for a plurality of searches and wherein said method further comprises the steps of: a. storing the average compression rate for all searches accomplished; and b. updating said average compression rate for all searches accomplished after accomplishing said step of locating said data.
References Cited (Backward Citations)
US3571576A
Cited
US3651483A
Cited
US3643226A
Cited
US4276597A
Cited
US3949420A
Cited
US4064489A
Cited
US4267568A
Cited
US4068298A
Cited
US4318184A
Cited
US4545032A
Cited
US4937779A
Cited
US4633393A
Cited
US4701745A
Cited
US4817036A
Cited
US4626829A
Cited
US4803651A
Cited
US5101487A
Cited
US4866440A
Cited
US4872009A
Cited
US4868570A
Cited
US4929946A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-05-16 | 1997-11-15 | 1998-05-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-05-16 | 2001-11-15 | 2002-05-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-05-16 | 2005-11-15 | 2006-05-17 | $7700.00 | Window Closed / Lapsed |