# US 2014/0156608 A1 · Efficiency of compression of data pages

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2014/0156608 A1
- Document ID: US20140156608A1
- Status: Published application
- Kind: A1
- Application number: 13/689,995
- Filed: 2012-11-30
- Published: 2014-06-05
- Earliest claimed: 2012-11-30
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: VENKATESH SAINATH
- Web page: https://patentgrep.com/patent/US20140156608A1

## CPC

- G06F 16/1744: {using compression, e.g. sparse files}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system includes a processor executing code to compress a first page of data stored in memory and calculate an effectiveness of the compression on the first page. The processor further, in response to the calculated compression effectiveness being at least equal to a pre-determined/pre-established compression effectiveness threshold: identifies a plurality of second pages of data from memory that have similarities in content with the first page; and sequentially performs subsequent compressions of second pages from among the plurality of second pages in an order that is based on a relative ranking of the plurality of second pages. The ranking of the second pages is according to a calculated differential parameter associated with each of the second pages, which indicates a level of similarity that exists between the first page and a corresponding second page. Higher ranked second pages are compressed ahead of lower rank second pages, yielding greater compression efficiency.

## Claims

### Claim at position 1

1-8. (canceled)

### Claim 9

A system for data compression, the system comprising:
a memory storage having a plurality of pages of data stored thereon;
a processor communicatively coupled to the memory storage and which executes program code that configures the processor to:
provide efficient compression of pages of data, the method comprising:
compress a first page of data stored in a memory;
calculate a compression effectiveness indicating an amount by which the first page was compressed; and
in response to the calculated compression effectiveness being at least as high as a pre-determined compression effectiveness threshold:
identify a plurality of second pages of data stored in the memory that have similarities in content with the first page; and
sequentially perform subsequent compressions of one or more second pages from among the plurality of second pages in an order that is based on a relative ranking of the plurality of second pages according to a differential parameter associated with each of the plurality of second pages that indicates a level of similarity that exists between the first page and a corresponding one of the plurality of second pages.

### Claim 10 (depends on 9)

The system of claim 9, wherein the program code that configures the processor to identify the plurality of second pages with similarities in content comprises code that configures the processor to execute functions of a memory de-duplication process by configuring the processor to:
compare each page of data within the memory with at least the first page to determine if the respective content of the two pages being compared are similar;
in response to identifying similar pages of data, compute a differential parameter value for each of the pages having similar content;
identify the first page as a root page;
generate and maintain an ordered mapping of the plurality of pages that have similarities in content with the first page, wherein the plurality of pages are arranged sequentially according to a relative size of the differential parameter value computed for each page when compared against the first page;
store the mapping within the memory; and
access the mapping to determine an order of selecting the one or more second pages on which to perform the subsequent compression.

### Claim 11 (depends on 9)

The system of claim 9, wherein the program code that configures the processor to identify the plurality of second pages with similarities in content comprises code that configures the processor to:
identify a second page of data stored in the memory;
calculate a differential parameter value indicating a relative similarity between the content of the first page and the content of the second page;
determine whether the differential parameter value is not greater than a pre-set differential parameter threshold that indicates a minimum level of similarity between any two pages that is sufficient to mark the two pages as similar; and
in response to determining that the differential parameter value is not greater than the differential parameter threshold, tag the second page of data as being similar to the first page;
perform the identifying, calculating, and determining for each second page of data stored in memory;
tag, as similar, only those second pages of data having a differential parameter value that is not greater than the differential parameter threshold; and
order the second pages that are tagged as being similar within a mapping that provides the plurality of second pages arranged in sequence of relative size of a respective differential parameter value for each of the plurality of second pages.

### Claim 12 (depends on 11)

The system of claim 11, wherein the pre-determined compression effectiveness threshold is indicative of a specific desired minimum value of compression effectiveness, and the program code comprises code that configures the processor to:
compare the calculated compression effectiveness against the pre-determined compression effectiveness threshold; and
in response to the calculated compression effectiveness being at least as high as the compression effectiveness threshold:
retrieve the mapping;
select at least one second page having a lowest differential parameter value;
perform a first subsequent compression on the selected at least one second page; and
perform each other subsequent compression on second pages selected in sequence based on the order within the mapping.

### Claim 13 (depends on 11)

The system of claim 11, wherein at least one of the pre-set differential parameter threshold and the pre-determined compression effectiveness threshold can be dynamically modified based on an amount of available memory, and the program code comprises code that configures the processor to modify a value of at least one of the pre-set differential parameter threshold and the pre-determined compression effectiveness threshold based on an amount of available memory, wherein the value of the differential parameter threshold and the value of the pre-determined compression effectiveness threshold are decreased in response to the amount of available memory being reduced and increases in response to the amount of available memory increasing.

### Claim 14 (depends on 9)

The system of claim 9, wherein the program code that configures the processor to calculate a compression effectiveness comprises code that configures the processor to calculate a ratio of (a) a difference between an original size of the first page and a compressed size of the first page to (b) the original size of the first page.

### Claim 15 (depends on 9)

The system of claim 9, further comprising code that configures the processor to:
rank each of the plurality of second pages according to a differential parameter value that indicates a relative similarity between the contents of each of the plurality of second pages and the first page;
generate at least one differential mapping comprising stored differential values of pairs of compared pages, wherein the differential mapping is a data structure indicating a differential value for each page of data in the memory compared to every other page of data in the memory; and
perform the identifying of the plurality of second pages utilizing the differential mapping.

### Claim 16 (depends on 15)

The system of claim 15, further comprising code that configures the processor to:
detect storage of a new page of data in the memory; and
in response to detecting the storage of the new page of data:
calculate new differential values for the new page of data compared to previously compressed pages of data;
determine whether any of the new differential values indicates that the new page of data is sufficiently similar to a compressed page; and
place the new page of data as one of the plurality of second pages within a differential mapping corresponding to the compressed page, wherein the new page of data is incorporated in a proper sequence within the differential mapping based on the new differential value relative to the existing differential values of the plurality of second pages.

### Claim 17

A computer program product comprising:
a computer-readable storage device having stored thereon computer program code executable by a processor to providing efficient compression of pages of data, the program code including code for:
compressing a first page of data stored in a memory;
calculating a compression effectiveness indicating an amount by which the first page was compressed;
in response to the calculated compression effectiveness being at least as high as a pre-determined compression effectiveness threshold:
identifying a plurality of second pages of data stored in the memory that have similarities in content with the first page; and
sequentially performing subsequent compressions of one or more second pages from among the plurality of second pages in an order that is based on a relative ranking of the plurality of second pages according to a differential parameter associated with each of the plurality of second pages that indicates a level of similarity that exists between the first page and a corresponding one of the plurality of second pages.

### Claim 18 (depends on 11)

The computer program product of claim 11, wherein the program code for identifying the plurality of pages with similarities in content comprises code for executing functions of a memory de-duplication process which includes code for:
comparing each page of data within the memory with at least the first page to determine if the respective content of the two pages being compared are similar;
in response to identifying similar pages of data, computing a differential parameter value for each of the pages having similar content;
identifying the first page as a root page;
generating and maintaining an ordered mapping of the plurality of pages that have similarities in content with the first page, wherein the plurality of pages are arranged sequentially according to a relative size of the differential parameter value computed for each page when compared against the first page;
storing the mapping within the memory; and
accessing the mapping to determine an order of selecting the one or more second pages on which to perform the subsequent compression.

### Claim 19 (depends on 17)

The computer program product of claim 17, wherein the program code for identifying the plurality of second pages of data comprises code for:
identifying a second page of data stored in the memory;
calculating a differential parameter value indicating a relative similarity between the content of the first page and the content of the second page;
determining whether the differential parameter value is not greater than a pre-set differential parameter threshold that indicates a minimum level of similarity between any two pages that is sufficient to mark the two pages as similar; and
in response to determining that the differential parameter value is not greater than the differential parameter threshold, tagging the second page of data as being similar to the first page;
performing the identifying, calculating, and determining for each second page of data stored in memory;
tagging, as similar, only those second pages of data having a differential parameter value that is not greater than the differential parameter threshold; and
ordering the second pages that are tagged as being similar within a mapping that provides the plurality of second pages arranged in sequence of relative size of a respective differential parameter value for each of the plurality of second pages.

### Claim 20 (depends on 19)

The computer program product of claim 19, wherein the pre-determined compression effectiveness threshold is indicative of a specific desired minimum value of compression effectiveness, and the program code further comprises code for:
comparing the calculated compression effectiveness against the pre-determined compression effectiveness threshold; and
in response to the calculated compression effectiveness being at least as high as the compression effectiveness threshold:
retrieving the mapping;
selecting at least one second page having a lowest differential parameter value;
performing a first subsequent compression on the selected at least one second page; and
performing each other subsequent compression on second pages selected in sequence based on the order within the mapping.

### Claim 21 (depends on 19)

The computer program product of claim 19, wherein at least one of the pre-set differential parameter threshold and the pre-determined compression effectiveness threshold can be dynamically modified based on an amount of available memory and the program code comprises code for changing a value of at least one of the pre-set differential parameter threshold and the pre-determined compression effectiveness threshold based on an amount of available memory, wherein the value of the differential parameter threshold and the value of the pre-determined compression effectiveness threshold are decreased in response to the amount of available memory being reduced and increases in response to the amount of available memory increasing.

### Claim 22 (depends on 17)

The computer program product of claim 17, wherein the program code for calculating a compression effectiveness comprises program code for calculating a ratio of (a) a difference between an original size of the first page and a compressed size of the first page to (b) the original size of the first page.

### Claim 23 (depends on 17)

The computer program product of claim 17, further comprising program code for:
ranking each of the plurality of second pages according to a differential parameter value that indicates a relative similarity between the contents of each of the plurality of second pages and the first page;
generating at least one differential mapping comprising stored differential values of pairs of compared pages, wherein the differential mapping is a data structure indicating a differential value for each page of data in the memory compared to every other page of data in the memory; and
performing the identifying of the plurality of second pages utilizing the differential mapping.

### Claim 24 (depends on 23)

The computer program product of claim 23, further comprising program code for:
detecting storage of a new page of data in the memory; and
in response to detecting the storage of the new page of data:
calculating new differential values for the new page of data compared to previously compressed pages of data;
determining whether any of the new differential values indicates that the new page of data is sufficiently similar to a compressed page; and
placing the new page of data as one of the plurality of second pages within a differential mapping corresponding to the compressed page, wherein the new page of data is incorporated in a proper sequence within the differential mapping based on the new differential value relative to the existing differential values of the plurality of second pages.