SYSTEM AND METHOD FOR COMPRESSION OF PARTIALLY ORDERED DATA SETS

• US 20100049726A1
• Filed: 08/19/2008
• Published: 02/25/2010
• Est. Priority Date: 08/19/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Agnihotri, Aditya, Yasa, Giridhar Appagi
• Granted Patent: US 8,250,043 B2
• Time in Patent Office: Days
• US Class Current: N/A
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A system and method for compression of partially ordered data sets is provided. A first record of the data set is compressed by encoding the record using a Fibonacci encoding technique. Thereafter, for each subsequent record N, the N−1^st record is subtracted from the N^th record before encoding the result, thereby allowing each subsequent record to store the difference (or delta) from the previous record.

Claims

1. A method for compressing a partially ordered data set, the method comprising the steps of:

(a) generating the partially ordered data set;

(b) selecting a first record from the partially ordered data set;

(c) compressing the first record;

(d) selecting a next record of the partially ordered data set;

(e) computing delta values of the selected next record; and

(f) compressing the computed delta values.

2. The method of claim 1 wherein the step of compressing the first record further comprises the step of encoding the first record using Fibonacci encoding.

3. The method of claim 1 wherein the step of computing the delta values further comprises the step of, for each element of the selected next record, subtracting a corresponding element from a previous record.

4. The method of claim 1 wherein the step of compressing the computed delta values further comprises the step of encoding the computed delta values suing Fibonacci encoding.

5. The method of claim 1 wherein the step of generating the partially ordered data set comprises the step of performing a data de-duplication procedure on a data set.

6. The method of claim 1 further comprising the step of performing steps (d)-(f) for a plurality of records of the partially ordered data set.

7. The method of claim 1 wherein the partially ordered data set comprises a set of unique identifiers.

8. The method of claim 7 wherein the unique identifiers comprise fingerprints.

9. A system for compressing a partially ordered data set, the system comprising:

a virtual tape library module configured to perform a data de-duplication procedure on a data set to produce the partially ordered data set and further configured to encode records of the partially ordered data set using a predefined encoding technique.

10. The system of claim 9 wherein the partially ordered data set comprises a descriptor list.

11. The system of claim 9 wherein the virtual tape library module is further configured to (i) select a next record, (ii) compute a set of delta values of the selected next record and (iii) compress the computed set of delta values.

12. The system of claim 11 wherein the virtual tape library is configured to compress the computed set of delta values by encoding the computed set of delta values using Fibonacci coding.

13. The system of claim 12 wherein the virtual tape library computes the set of delta values of the selected next record by subtracting an immediately previous record from the selected next record to generate the delta values.

14. The system of claim 9 wherein the data set comprises tape backup data stream.

15. The system of claim 9 wherein the virtual tape library is further configured to stored the encoded records on a storage device.

16. The system of claim 11 wherein each record, other than a first record, is stored as a difference from a previous record.

17. The system of claim 11 wherein the predefined encoding technique comprises Fibonacci coding.

18. A method for compressing a partially ordered list of records, the method comprising:

encoding a first record using a Fibonacci encoding technique;

for each subsequent record N, subtracting the N−

1^st record from the Nth record, to generate a difference; and

encoding each difference using the Fibonacci encoding technique.

19. The method of claim 18 wherein the partially ordered list of records comprises fingerprints.

20. The method of claim 18 further comprising storing the encoded first record and differences as a descriptor list.