Data compression method and apparatus

• US 20050192994A1
• Filed: 04/20/2005
• Published: 09/01/2005
• Est. Priority Date: 12/10/1998
• Status: Active Grant

• Current Assignee: Donald F. Caldwell, Glenn Stephen Fowler, Kenneth Ward Church
• Original Assignee: Donald F. Caldwell, Glenn Stephen Fowler, Kenneth Ward Church
• Inventors: Church, Kenneth Ward, Caldwell, Donald F., Fowler, Glenn Stephen
• Granted Patent: US 7,720,878 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational 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: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An improved data compression method and apparatus is provided, particularly with regard to the compression of data in tabular form such as database records. The present invention achieves improved compression ratios by utilizing metadata to transform the data in a manner that optimizes known compression techniques. In one embodiment of the invention, a schema is generated which is utilized to reorder and partition the data into low entropy and high entropy portions which are separately compressed by conventional compression methods. The high entropy portion is further reordered and partitioned to take advantage of row and column dependencies in the data. The present invention enables not only much greater compression ratios but increased speed than is achieved by compressing the untransformed data.

Claims

1. A method for improving compression of a stream of data comprising:

transforming the data in accordance with a schema to form a first portion and a second portion; and

separately transforming the first portion and the second portion to form a transformed output that includes the transformed first portion and the transformed second portion.

2. The method of claim 1 wherein the first portion contains low entropy data and said second portion contains high entropy data.

3. The method of claim 1 wherein the data is tabular data, and the transformation step further comprises the step of reordering the data into column major order.

4. The method of claim 3 wherein the transformation step further comprises the step of partitioning the data into columns which are separately compressed.

5. A method for retrieving a stream of data from a stream of compressed data which has been compressed in accordance with claim 1, the method comprising:

decompressing the compressed data to form a first decompressed portion and a second decompressed portion; and

transforming the first decompressed portion and the second decompressed portion in accordance with a provided schema to combine the first decompressed portion and the second decompressed portion and obtain thereby said stream of data.

11. The method of claim 1 further comprising a step of receiving said schema.

12. The method of claim 1 further comprising a step of developing said schema from said data.

13. The method of claim 2 further comprising a step of developing said schema from said data by:

partitioning a subset of the data of the second portion into columns; and

identifying combinations of columns that minimize the compressed size of the sample.

14. The method of claim 1 wherein the transformation step comprises a step of partitioning the data into a first portion and second portion based on entropy of the data.

15. The method of claim 1 where the schema pertains to entropy of the data.

16. The method of claim 1 where the schema informs how to reorder the data to enable partitioning of the data into a low entropy portion and a high entropy portion.

6. A method for generating a schema for improving compression of a stream of data comprising:

separating a sample of the data into a first portion of low entropy and a second portion of high entropy;

partitioning the second portion into columns;

identifying combinations of columns that minimize the compressed size of the sample.

7. An apparatus for improved compression of a stream of data comprising:

means for transforming the data in accordance with a schema to form a first portion and a second portion; and

means for compressing the first portion separately and for separately compressing the second portion.

8. The apparatus of claim 7 wherein the transforming means causes said first portion to contain low entropy data and said second portion to contain high entropy data.

9. The apparatus of claim 7 wherein the transforming means comprises means for reordering the data into column major order.

10. The apparatus of claim 9 wherein the transforming means comprises means for partitioning the data into columns which are separately compressed.