# US 11,308,093 B1 · Encoding scheme for numeric-like data types

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

- Number: US 11,308,093 B1
- Document ID: US11308093B1
- Status: Granted
- Kind: B1
- Application number: 16/714,576
- Filed: 2019-12-13
- Granted: 2022-04-19
- Earliest claimed: 2019-12-13
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: Orestis Polychroniou; Naresh Chainani; Ippokratis Pandis
- Web page: https://patentgrep.com/patent/US11308093B1

## CPC

- G06F 16/174: Redundancy elimination performed by the file system (error detection or correction of the data by redundancy in operations G06F11/14)
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F 16/1744: {using compression, e.g. sparse files}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 16/23: Updating
- G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)}
- G06F 16/2455: Query execution
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method includes encoding, by an encoding engine, consecutive sections of a received data stream that includes a stream of values. The encoding includes identifying a minimum value in a section of the stream. The encoding includes determining, for each value in the section of the stream, respective differences with the minimum value. An encoded version of the section includes the minimum value and a mask value. The mask value is combined with respective portions of the respective differences to generate the respective differences of each value in the section. The encoded version of the section further includes the respective portions of the respective differences.

## Claims

### Claim 1

A system, comprising:
at least one processor; and
a memory, storing program instructions that when executed by the at least one processor, cause the at least one processor to implement an encoding engine, the encoding engine configured to:
receive an input data stream that includes a stream of values;
encode consecutive sections of the input data stream into respective frames, wherein to encode the input data stream in individual ones of the frames, the encoding engine is configured to:
identify a minimum value in one of the sections of the stream;
determine, for each value in the one section of the stream, respective differences with the minimum value;
store in the frame for the one section:
the minimum value;
a mask value that is combined with respective portions of the respective differences to generate the respective differences of each value in the one section; and
the respective portions of the respective differences.

### Claim 2 (depends on 1)

The system of claim 1,
wherein the encoding engine is further configured to:
identify a different minimum value in a subsequent section of the stream;
determine, for each value in the subsequent section of the stream, respective differences with the different minimum value;
store in the frame for the subsequent section:
the second minimum value;
a second mask value that is combined with respective portions of the respective differences to generate the respective differences of each value in the subsequent section; and
the respective portions of the respective differences.

### Claim 3 (depends on 2)

The system of claim 2, wherein the minimum value in the one section of the stream is different from the second minimum value in the subsequent section of the stream.

### Claim 4 (depends on 1)

The system of claim 1, wherein storing in the frame for the one section includes:
storing the mask value as an initial value in the frame;
storing the minimum value as a next value in the frame; and
storing respective portions of the respective differences as subsequent values in the frame.

### Claim 5

A method, comprising:
encoding, by an encoding engine, consecutive sections of a received data stream that includes a stream of values, comprising:
identifying a minimum value in a section of the stream;
determining, for each value in the section of the stream, respective differences with the minimum value;
including in an encoded version of the section:
the minimum value;
a mask value that is combined with respective portions of the respective differences to generate the respective differences of each value in the section; and
the respective portions of the respective differences.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
storing the encoded version of the section in a data block; and
storing a null bitmap in the data block, the null bitmap identifying null values in the received data stream.

### Claim 7 (depends on 6)

The method of claim 6, wherein the encoded version of the section is stored in one portion of a data block, and wherein the null bitmap is stored in another portion of the data block.

### Claim 8 (depends on 7)

The method of claim 7, wherein the storing of the encoded version of the section and the storing of the null bitmap are performed in parallel.

### Claim 9 (depends on 6)

The method of claim 6, further comprising compressing the null bitmap using a run-length-encoding (RLE) technique.

### Claim 10 (depends on 6)

The method of claim 6, wherein:
the received data stream includes null values and non-null values;
the encoded version of the section includes exclusively non-null values; and
the null values in the received data stream are identified using the null bitmap.

### Claim 11 (depends on 5)

The method of claim 5, further comprising:
decoding, by the encoding engine, the encoded version of the section responsive to receiving a query, the decoding comprising:
identifying the minimum value and the mask value in the encoded version of the section;
applying the mask value to the respective portions of the respective differences to determine the respective differences of each value in the section;
determining, based on the minimum value and the respective differences, each value in the section; and
providing each value in the section in response to the query.

### Claim 12 (depends on 8)

The method of claim 8, wherein the decoding includes utilizing a single instruction, multiple data (SIMD) instruction set to determine each value in the section.

### Claim 13 (depends on 12)

The method of claim 12, wherein the SIMD instruction set corresponds to an Advanced Vector Extensions 2 (AVX 2) instruction set or an Advanced Vector Extensions (AVX) 512-bit SIMD instruction set.

### Claim 14 (depends on 5)

The method of claim 5, wherein the section of the stream includes a particular number of values, the particular number of values corresponding to at least sixty four (64) values.

### Claim 15 (depends on 14)

The method of claim 14, wherein the section of the stream and a next consecutive section of the stream each include a fixed number of values corresponding to the particular number of values.

### Claim 16

One or more non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to implement:
obtaining a data stream that includes a stream of values;
encoding consecutive sections of the data stream, wherein, in encoding the consecutive sections of the data stream, the program instructions cause the one or more computing devices to implement:
identifying a minimum value in a section of the stream;
determining, for each value in the section of the stream, respective differences with the minimum value;
including in an encoded version of the section:
the minimum value;
a mask value that is combined with respective portions of the respective differences to generate the respective differences of each value in the section; and
the respective portions of the respective differences.

### Claim 17 (depends on 16)

The one or more non-transitory, computer-readable storage media of claim 16, wherein a subsequent section of the stream includes exclusively non-null values, and wherein an additional byte is stored to identify the subsequent section as including exclusively non-null values.

### Claim 18 (depends on 16)

The one or more non-transitory, computer-readable storage media of claim 16, wherein a subsequent section of the stream includes exclusively null values, and wherein an additional byte is stored to identify the subsequent section as including exclusively null values.

### Claim 19 (depends on 16)

The one or more non-transitory, computer-readable storage media of claim 16, wherein a subsequent section of the stream includes repeating non-null values, and wherein a run-length-encoding (RLE) technique is used to compress the repeating non-null values.

### Claim 20 (depends on 16)

The method of claim 16, wherein a subsequent section of the stream includes repeating null values, and wherein a run-length-encoding (RLE) technique is used to compress the repeating null values.