Method and apparatus for utilizing patterns in data to reduce file size

• US 9,298,799 B1
• Filed: 09/14/2012
• Issued: 03/29/2016
• Est. Priority Date: 12/11/2002
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Pedersen, Bruce, Park, Jim, Kazarian, Peter
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US13/620,338
• Time in Patent Office: 1,292 Days
• Field of Search: 707/693
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: H03M 7/3079 Context modeling
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/707 Structured documents, e.g. XML

Abstract

A method for managing records in an object-oriented database is disclosed. Modified representations of data in fields of records is generated in response to patterns in the data. The modified representations of the data is compressed utilizing similarities in the modified representations of the data.

Claims

1. A method for managing records, comprising:

generating modified representations of data in fields of the records by taking an arithmetic difference between data in fields of a record and data in corresponding fields of a previous instance of the record, wherein a location of the previous instance of the record and a location of a next instance of the record are identified in the fields of the records; and

compressing the modified representations of the data utilizing similarities between values within the modified representations of the data, wherein at least one of the generating and the compressing is performed by a processor.

2. The method of claim 1 further comprising identifying patterns in the modified representations of the data.

3. The method of claim 1, wherein generating the modified representations of the data comprises:

generating a first record having fields with zero-initialized values;

designating the first record as an initial instance of the records;

generating arithmetic differences between data in each field of each record and data in corresponding fields from previous instances of the records; and

designating the arithmetic differences as representations of the data in the fields.

4. The method of claim 1 further comprising assigning a special identifier (ID) to a first instance of a record.

5. The method of claim 1, wherein compressing the modified representations of the data utilizing similarities in the modified representations of the data comprises utilizing a dictionary-based compression technique.

6. The method of claim 1 further comprising transmitting compressed modified representations of the data to a destination.

7. The method of claim 1 further comprising:

de-compressing the modified representations of the data; and

converting the modified representations of the data back to an original representation of the data.

8. The method of claim 7, wherein de-compressing the modified representations of the data, and converting the modified representations of the data is performed in a memory of a computer system.

9. The method of claim 1 further comprising for each record of the records, converting pointer values that point to memory addresses of a next record and a previous record to identification numbers associated with the next record and the previous record.

10. A non-transitory machine readable medium including sequences of instructions, stored thereon for causing a machine to execute a method comprising:

generating modified representations of data in fields of records by taking an arithmetic difference between data in fields of a record and data in corresponding fields of a previous instance of the record, wherein a location of the previous instance of the record and a location of a next instance of the record are identified in the fields of the records; and

compressing the modified representations of the data utilizing similarities between values within the modified representations of the data.

11. The non-transitory machine readable medium of claim 10, wherein generating modified representations of the data comprises:

generating a first record having fields with zero-initialized values;

designating the first record as an initial instance of the records;

generating arithmetic differences between data in each field of each record and data in corresponding fields from previous instances of the record; and

designating the arithmetic differences as representations of the data.

12. The non-transitory machine readable medium of claim 10, wherein the method further comprises assigning a special identifier (ID) to a first instance of a record.

13. The non-transitory machine readable medium of claim 10, wherein compressing modified representations of the data utilizing similarities in the modified representations of the data comprises utilizing a dictionary-based compression technique.

14. The non-transitory machine readable medium of claim 10, wherein the method further comprises:

de-compressing the modified representations of the data; and

converting the modified representations of the data back to an original representation of the data.

15. The non-transitory machine readable medium of claim 14, wherein de-compressing the modified representations of the data, and converting the modified representations of the data is performed in a memory of a computer system.

16. The non-transitory machine readable medium of claim 10 further comprising for each record of the records, converting pointer values that point to memory addresses of a next record and a previous record to identification numbers associated with the next record and the previous record.

17. A compression pre-processing unit, comprising:

a processor;

a pointer array that identifies, from a perspective of a record, a previous instance of the record and a next instance of the record;

a data modification unit that converts pointer values that point to memory addresses of the next instance of the record and the previous instance of the record to identification numbers associated with the next instance of the record and the previous instance of the record and that generates modified representations of data in the record in response to data in the previous instance of the record; and

an output unit that compresses the modified representation of the data in the record utilizing similarities between values within the modified representations of the data.

18. The compression pre-processing unit of claim 17, wherein the data modification unit generates the modified representation of data by taking an arithmetic difference between the data in the record and the data in the previous instance of the record.

19. The compression pre-processing unit of claim 17 further comprising a record processor that determines a type of the record.

20. The compression pre-processing unit of claim 17, wherein the output unit writes the modified representation of the data to a file.