Method and apparatus for improving a compression ratio of multiple documents by using templates

• US 9,390,099 B1
• Filed: 03/29/2011
• Issued: 07/12/2016
• Est. Priority Date: 03/29/2011
• Status: Active Grant

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Wu, Zhongqiang, Wang, Chen, Dimitrov, Rossen
• Primary Examiner(s): Huang, Miranda
• Application Number:
  US13/074,559
• Time in Patent Office: 1,932 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• 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/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/707 Structured documents, e.g. XML

Abstract

Example embodiments of the present invention effectively manage a large set of records such that each can be quickly accessed while still reducing the system capacity used for storing the records by taking into account specifics of the record structure. A template document is constructed for a large set of similar documents, such that it represents the maximum common portion of content in the document set. The template is compressed and stored. Every document in the set is then concatenated individually to the uncompressed template and the concatenated result is compressed. The compressed template is then subtracted from the combined compressed result. The result of this subtraction is stored in the data store for each document. Effectively, only the compressed difference between each document and the template is stored, which reduces significantly the amount of capacity necessary for storing the document set (e.g., by a factor of 5 or 10).

Claims

1. A computer-implemented method comprising:

concatenating a data object in a set of data objects with a template for the set of data objects;

compressing the concatenated data object/template pair; and

determining a difference between the compressed concatenated data object/template pair and a compressed version of the template for the set of data objects.

2. The method of claim 1

wherein the set of data objects comprises a set of metadata records;

wherein the template for the set of data objects comprises a metadata template for the set of metadata templates; and

wherein compressing the concatenated data object/template pair comprises;

compressing a metadata record in the set of metadata records; and

compressing a metadata template for the set of metadata templates.

3. The method of claim 2 wherein the set of metadata records is a set of XML documents.

4. The method of claim 1 wherein the data object is constructed from the template.

5. The method of claim 4 wherein compressing the concatenated data object/template pair comprises matching keywords in the data object to keywords in the template.

6. The method of claim 1 wherein determining a difference between the compressed concatenated data object/template pair and a compressed version of the template for the set of data objects comprises removing a binary portion of the compressed concatenated data object/template pair that is equivalent to the compressed version of the template.

7. The method of claim 1 further comprising:

concatenating the compressed version of the template for the set of data objects and the difference between the compressed concatenated data object/template pair and the compressed version of the template for the set of data objects;

decompressing the concatenated compressed template/difference pair; and

disjoining the template for the set of data objects from the decompressed concatenated compressed template/difference pair.

8. The method of claim 1 further comprising mapping the difference between the compressed concatenated data object/template pair and the compressed version of the template for the set of data objects to the template for the set of data objects to decompress the data object.

9. A system comprising:

a data store; and

a computer including memory storing computer-executable logic that, when executed by the computer, causes the computer to perform the operations of;

concatenating a data object in a set of data objects with a template for the set of data objects;

compressing the concatenated data object/template pair; and

determining a difference between the compressed concatenated data object/template pair and a compressed version of the template for the set of data objects.

10. The system of claim 9

wherein the set of data objects comprises a set of metadata records;

wherein the template for the set of data objects comprises a metadata template for the set of metadata templates; and

wherein compressing the concatenated data object/template pair comprises;

compressing a metadata record in the set of metadata records in the data store, and

compressing a metadata template for the set of metadata templates.

11. The system of claim 10 wherein the set of metadata records in the data store is a set of XML documents in the data store.

12. The system of claim 9 wherein the data object is constructed from the template.

13. The system of claim 12 wherein compressing the concatenated data object/template pair comprises matching keywords in the object to keywords in the template.

14. The system of claim 9 wherein determining a difference between the compressed the concatenated data object/template pair and a compressed version of the template for the set of data objects comprises removing the binary portion of the compressed the concatenated data object/template pair that is equivalent to the compressed version of the template.

15. The system of claim 9 wherein the memory further stores computer-executable logic that, when executed by the computer, causes the computer to perform the further operations of:

concatenating the compressed version of the template for the set of data objects and the difference between the compressed the concatenated data object/template pair and the compressed version of the template for the set of data objects;

decompressing the concatenated compressed template/difference pair; and

disjoining the template for the set of data objects from the decompressed concatenated compressed template/difference pair.

16. The system of claim 9 wherein the memory further stores computer-executable logic that, when executed by the computer, causes the computer to perform the further operation of mapping the difference between the compressed the concatenated data object/template pair and the compressed version of the template for the set of data to the template for the set of data objects to decompress the data object.

17. A computer program product including a non-transitory computer-readable storage medium encoded with computer program code that, when executed on a processor of a computer, causes the computer to perform template based compression, the computer program product comprising:

computer program code for concatenating a data object in a set of data objects with a template for the set of data objects;

computer program code for compressing the concatenated data object/template pair; and

computer program code for determining a difference between the compressed concatenated data object/template pair and a compressed version of the template for the set of data objects.

18. The computer program product of claim 17

wherein the set of data objects comprises a set of metadata records;

wherein the template for the set of data objects comprises a metadata template for the set of metadata templates; and

wherein computer program code for compressing the concatenated data object/template pair comprises;

computer program code for compressing a metadata record in the set of metadata records; and

computer program code for compressing a metadata template for the set of metadata templates.

19. The computer program product of claim 18 wherein computer program code for determining a difference between the compressed concatenated data object/template pair and a compressed version of the template for the set of data objects comprises computer program code for removing a binary portion of the compressed concatenated data object/template pair that is equivalent to the compressed version of the template.

20. The computer program product of claim 17 further comprising:

computer program code for concatenating the compressed version of the template for the set of data objects and the difference between the compressed concatenated data object/template pair and the compressed version of the template for the set of data objects;

computer program code for decompressing the concatenated compressed template/difference pair; and

computer program code for disjoining the template for the set of data objects from the decompressed concatenated compressed template/difference pair.