US 6,959,300 B1 · Data compression method and apparatus

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.

Claims4

Dependent claims

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

transforming the data in accordance with a schema;
and
compressing the transformed data;
wherein the transformation step further comprises the step of reordering the data into column major order.

1 more element

Dependencies are inferred from the claim text.

Facts

Application

09/383,889Filed 26 Aug 1999 · us provisional application

Priority

10 Dec 1998

Granted

25 Oct 2005

Term ends

Not estimatedThe source records don’t support an estimate.

Classification7 codes

H03M 7/30
Conversion of a code where information is represented by a given sequence or number of digits to a code where the same , similar or subset of…:…
G06F 16/20
Information retrieval; Database structures therefor; File system structures therefor: of structured data, e.g. relational data
H03M 7/3084
Compression ; Expansion; Suppression of unnecessary data, e.g. redundancy reduction: using adaptive string matching, e.g. the Lempel-Ziv method
Y10S 707/99942
Database schema or data structure: manipulating data structure, e.g. compression, compaction, compilation

Data compression method and apparatus

Life of this patent

Data compression method and apparatus

Life of this patent

Abstract

Claims4