# US 9,519,651 B2 · Hierarchical data compression and computation

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

- Number: US 9,519,651 B2
- Document ID: US9519651B2
- Status: Granted
- Kind: B2
- Application number: 15/077,262
- Filed: 2016-03-22
- Published: 2016-07-14
- Granted: 2016-12-13
- Earliest claimed: 2014-09-30
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: William B. Ackerman; Garth A. Dickie; Jeffrey M. Keller
- Web page: https://patentgrep.com/patent/US9519651B2

## CPC

- G06F 16/1744: {using compression, e.g. sparse files}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/2456: {Join operations}
- G06F 16/9535: Search customisation based on user profiles and personalisation
- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- H03M 7/46: Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
- H03M 7/6011: {Encoder aspects}
- H03M 7/6035: {Handling of unkown probabilities}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

According to embodiments of the present invention, machines, systems, methods and computer program products for hierarchical compression of data are presented comprising creating a compression hierarchy of compression nodes, wherein each compression node is associated with a compression operation to produce compressed data. An output of any of the compression nodes may be compressed by another compression node or the same compression node. A path of one or more compression nodes is determined through said compression hierarchy based upon compression statistics to compress data, and the data is compressed by the compression nodes of the path. Various computational techniques are presented herein for manipulating the compression hierarchy to defer or reduce computation during query evaluation.

## Claims

### Claim 1

A method of hierarchical compression comprising:
creating a compression hierarchy of compression nodes, wherein each compression node is associated with a compression operation to produce compressed data, and wherein creating the compression hierarchy of compression nodes comprises:
creating a run length encoding compression node in the compression hierarchy;
determining a path of one or more compression nodes through said compression hierarchy, based upon compression statistics, to compress data; and
compressing the data by the compression nodes of the path, wherein compressing the data comprises:
performing part of a join operation on the data using the run length encoding compression node, wherein the join operation is performed by applying input data to a values field of the run length encoding compression node and by applying repeat counts to a lengths field of the run length encoding compression node.

### Claim 2 (depends on 1)

The method of claim 1, further comprising selecting a path of the compression hierarchy having a measure of compression higher than any of the other paths.

### Claim 3 (depends on 1)

The method of claim 1, wherein the compression nodes are configured to compress one or more data types selected from a group consisting of: integer, character and double.

### Claim 4 (depends on 1)

The method of claim 1, wherein each compression node is selected from a group consisting of: a bitshaved compression node, a dictionary compression node, a run length encoding compression node, a character-based compression node and a delta compression node.