# US 12,602,363 B1 · Overlay bitmaps for indexing and querying data

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

- Number: US 12,602,363 B1
- Document ID: US12602363B1
- Status: Granted
- Kind: B1
- Application number: 18/955,741
- Filed: 2024-11-21
- Granted: 2026-04-14
- Earliest claimed: 2024-11-21
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Gunes Aluc
- Web page: https://patentgrep.com/patent/US12602363B1

## CPC

- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 16/278: {Data partitioning, e.g. horizontal or vertical partitioning}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments of the present disclosure include techniques for encoding data locations in a database using bit maps. In one embodiment, a plurality of bit maps are generated for unique values in a column of a table. The bit maps may be ordered in columns, where columns correspond to unique values a particular table column. Bit maps for each comprise a first binary value when table value in a corresponding row matches a corresponding bit map unique value. Bit map values are set to a second binary value opposite the first binary value when the bit map unique value does not match the table row value for previous bit maps and don't care values for subsequent bit maps. In one embodiment, the bit maps are ordered by bit density.

## Claims

### Claim 1

A computer implemented method comprising:
partitioning a table into one or more row groups comprising a number of rows;
determining, for a particular column of each row group, a plurality of unique values;
forming a bit map table comprising bit map columns corresponding to each unique value and bit map rows corresponding to the number of rows of the row group, wherein columns of the bit map table correspond to unique values in rows of the particular column, wherein rows of the bit map table comprise one first binary value when a row of the particular column matches a corresponding bit map table column unique value, and wherein column values, for each row of the bit map table, up to the first binary value comprise a second binary value opposite the first binary value and after the first binary value comprise don't care values;
forming a bit map string comprising successive columns of the bit map table, the bit map string comprising the first and second binary values, but not the don't care values, from each column; and
successively decoding each bit map, wherein each decoded bit map is used to decode a subsequent encoded bit map.

### Claim 2 (depends on 1)

The method of claim 1, wherein each column of the bit map table corresponds to a different bit map.

### Claim 3 (depends on 2)

The method of claim 2, wherein each bit map comprises associated metadata.

### Claim 4 (depends on 3)

The method of claim 3, wherein the metadata comprises a binary code uniquely representing the one of the unique values.

### Claim 5 (depends on 3)

The method of claim 3, wherein the metadata comprises header bits in front of the bit map and footer bits at the end of the bit map.

### Claim 6 (depends on 1)

The method of claim 1, wherein the columns of the bit map table are ordered according to decreasing bit density from a first column to a last column.

### Claim 7 (depends on 1)

The method of claim 1, wherein said decoding is according to decreasing bit density order.

### Claim 8 (depends on 1)

The method of claim 1, wherein successively decoding comprises combining bits of an inverted first bit map with bits of one or more subsequent encoded bit maps to produce a decoded bit map.

### Claim 9 (depends on 8)

The method of claim 8, wherein combining bits uses an overlay function.

### Claim 10 (depends on 8)

The method of claim 8, wherein combining bits comprises:
when a bit of the inverted first bit map is 1 and bits of the one or more subsequent encoded bit maps are 1, a bit of the decoded bit map is 1;
when the bit of the inverted first bit map is 1 and a bit of one of the one or more subsequent bit maps is 0, the bit of the decoded bit map is 0; and
when a bit of an inverted previous bit map is 0, the remaining values of the one or more subsequent bit maps are shifted by one and the bit of the decoded bit map is 0.

### Claim 11

A computer system comprising:
at least one processor;
at least one non-transitory computer-readable medium storing computer-executable instructions that, when executed by the at least one processor, cause the computer system to execute a method comprising:
partitioning a table into one or more row groups comprising a number of rows;
determining, for a particular column of each row group, a plurality of unique values;
forming a bit map table comprising bit map columns corresponding to each unique value and bit map rows corresponding to the number of rows of the row group, wherein columns of the bit map table correspond to unique values in rows of the particular column, wherein rows of the bit map table comprise one first binary value when a row of the particular column matches a corresponding bit map table column unique value, and wherein column values, for each row of the bit map table, up to the first binary value comprise a second binary value opposite the first binary value and after the first binary value comprise don't care values; and
forming a bit map string comprising successive columns of the bit map table, the bit map string comprising the first and second binary values, but not the don't care values, from each column; and
successively decoding each bit map, wherein each decoded bit map is used to decode a subsequent encoded bit map.

### Claim 12 (depends on 11)

The computer system of claim 11, wherein each column of the bit map table corresponds to a different bit map.

### Claim 13 (depends on 12)

The computer system of claim 12, wherein each bit map comprises associated metadata.

### Claim 14 (depends on 13)

The computer system of claim 13, wherein the metadata comprises a binary code uniquely representing the one of the unique values.

### Claim 15 (depends on 11)

The computer system of claim 11, wherein successively decoding comprises successively decoding each bit map according to decreasing bit density order.

### Claim 16

A non-transitory computer-readable medium storing computer-executable instructions that, when executed by at least one processor of a computer system, cause the computer system to execute method comprising:
partitioning a table into one or more row groups comprising a number of rows;
determining, for a particular column of each row group, a plurality of unique values;
forming a bit map table comprising bit map columns corresponding to each unique value and bit map rows corresponding to the number of rows of the row group, wherein columns of the bit map table correspond to unique values in rows of the particular column, wherein rows of the bit map table comprise one first binary value when a row of the particular column matches a corresponding bit map table column unique value, and wherein column values, for each row of the bit map table, up to the first binary value comprise a second binary value opposite the first binary value and after the first binary value comprise don't care values; and
forming a bit map string comprising successive columns of the bit map table, the bit map string comprising the first and second binary values, but not the don't care values, from each column; and
successively decoding each bit map, wherein each decoded bit map is used to decode a subsequent encoded bit map.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein successively decoding comprises combining bits of an inverted first bit map with bits of one or more subsequent encoded bit maps to produce a decoded bit map.

### Claim 18 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein each column of the bit map table corresponds to a different bit map.

### Claim 19 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein the columns of the bit map table are ordered according to decreasing bit density from a first column to a last column.