# US 2023/0267108 A1 · Feedback-based inverted index compression

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

- Number: US 2023/0267108 A1
- Document ID: US20230267108A1
- Status: Published application
- Kind: A1
- Application number: 17/676,925
- Filed: 2022-02-22
- Published: 2023-08-24
- Earliest claimed: 2022-02-22
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Torsten AMUNDSEN; Pavel SUKHOV
- Web page: https://patentgrep.com/patent/US20230267108A1

## CPC

- G06F 16/2272: {Management thereof}
- G06F 16/319: {Inverted lists}
- H03M 7/607: {Selection between different types of compressors}
- 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

The disclosed technology is generally directed to the compression of inverted indexes. In one example of the technology, an inverted index that includes a plurality of posting lists and metadata is provided. The inverted index indicates compression settings that are associated with the plurality of posting lists. At periodic scheduled times, a regeneration is performed on the inverted index. The regeneration includes decompressing the inverted index. The decompressing uses the compression settings indicated by the inverted index. The regeneration further includes determining compression settings to use during a next periodic scheduled time of the plurality of periodic scheduled times, such that at least a first posting list of the plurality of posting lists uses a different compression setting than a second posting list of the plurality of posting lists.

## Claims

### Claim 1

An apparatus, comprising:
a device including at least one memory having processor-executable code stored therein, and at least one processor that is adapted to execute the processor-executable code, wherein the processor-executable code includes processor-executable instructions that, in response to execution, enable the device to perform actions, including:
providing an inverted index that includes a plurality of posting lists and metadata, wherein the inverted index indicates compression settings that are associated with the plurality of posting lists;
at plurality of periodic scheduled times, performing a regeneration on the inverted index, the regeneration including:
decompressing the inverted index, wherein the decompressing uses the compression settings indicated by the inverted index; and
determining compression settings to use during a next periodic scheduled time of the plurality of periodic scheduled times, such that at least a first posting list of the plurality of posting lists uses a different compression setting than a second posting list of the plurality of posting lists.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein determining the compression settings to use during the next periodic scheduled time includes determining which compression scheme of a plurality of compression schemes to use to compress the posting list during the next periodic scheduled time.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein determining the compression settings to use during the next periodic scheduled time includes determining a K value of a Rice-Golomb2 compression scheme to use to compress the posting list during the next time periodic scheduled time.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein performing the regeneration on the inverted index includes merging the inverted index with at least one additional index.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the inverted index indicates, for each posting list of the plurality of posting lists, compression settings of that posting list, such that the compression settings of each of the posting lists is individually selectable.

### Claim 6 (depends on 5)

The apparatus of claim 5, wherein determining compression settings to use during the next periodic scheduled time of the plurality of periodic scheduled times includes determining, for each posting list of the plurality of posting lists, compression settings to use for that posting list during the next periodic scheduled time.

### Claim 7 (depends on 5)

The apparatus of claim 5, wherein determining compression settings to use during the next periodic scheduled time of the plurality of periodic scheduled times includes determining, for each posting list of the plurality of posting lists, compression settings to use for that posting list during the next periodic scheduled time by testing a plurality of compression settings for that posting list and selecting the compression settings based on the compression settings that provide the best compression based on at least one of storage space of the compressed posting list, a speed of compressing the posting list, or a speed of decompressing the posting list.

### Claim 8 (depends on 5)

The apparatus of claim 5, wherein determining compression settings to use during the next periodic scheduled time of the plurality of periodic scheduled times includes determining, for each posting list of the plurality of posting lists, determining whether a K value of a Rice-Golom13 compression scheme to use to compress that posting list during the next time periodic scheduled time should be incremented by one, decremented by one, or left unchanged.

### Claim 9 (depends on 8)

The apparatus of claim 8, wherein for each posting list of the plurality of posting lists, determining whether the K value of the Rice-Golom13 compression scheme to use to compress that posting list during the next time periodic scheduled time should be incremented by one, decremented by one, or left unchanged is accomplished by selecting from among the actions of incrementing the K value by one, decrementing the K value by one, or leaving the K value unchanged based on which of the actions, upon compression of the posting list using that K value, would cause the compressed posting list to have the shortest length.

### Claim 10

A method, comprising:
at each scheduled time of a plurality of scheduled times, performing a regeneration on an index, wherein the index indicates compression settings that are associated with the plurality of posting lists, and wherein the regeneration includes:
decompressing the index, wherein the decompressing uses the compression settings indicated by the index; and
via a processor, determining compression settings to use during a next scheduled time of the plurality of scheduled times, such that at least a first posting list of the plurality of posting lists uses a different compression setting than a second posting list of the plurality of posting lists.

### Claim 11 (depends on 10)

The method of claim 10, wherein the index is an inverted index.

### Claim 12 (depends on 10)

The method of claim 10, wherein performing the regeneration on the index includes merging the index with at least one additional index.

### Claim 13 (depends on 10)

The method of claim 10, wherein the index indicates, for each posting list of the plurality of posting lists, compression settings of that posting list, such that the compression settings of each of the posting lists is individually selectable.

### Claim 14 (depends on 13)

The method of claim 13, wherein determining compression settings to use during the next scheduled time of the plurality of scheduled times includes determining, for each posting list of the plurality of posting lists, compression settings to use for that posting list during the next scheduled time of the plurality of scheduled times.

### Claim 15 (depends on 13)

The method of claim 13, wherein determining compression settings to use during the next scheduled time of the plurality of scheduled times includes determining, for each posting list of the plurality of posting lists, determining whether a K value of a Rice-Golom13 compression scheme to use to compress that posting list during the next scheduled time should be incremented by one, decremented by one, or left unchanged.

### Claim 16

A processor-readable storage medium, having stored thereon processor-executable code that, upon execution by at least one processor, enables actions, comprising:
accessing an index that includes a plurality of posting lists and metadata, wherein the index indicates compression settings that are associated with the plurality of posting lists;
at predetermined times, regenerating the index, the regenerating including:
decompressing the index, wherein the decompressing uses the compression settings indicated by the index; and
determining compression settings to use during a next predetermined time of the predetermined times, such that at least a first posting list of the plurality of posting lists uses a different compression setting than a second posting list of the plurality of posting lists.

### Claim 17 (depends on 16)

The processor-readable storage medium of claim 16, wherein the index is an inverted index.

### Claim 18 (depends on 16)

The processor-readable storage medium of claim 16, wherein regenerating the index includes merging the index with at least one additional index.

### Claim 19 (depends on 16)

The processor-readable storage medium of claim 16, wherein the index indicates, for each posting list of the plurality of posting lists, compression settings of that posting list, such that the compression settings of each of the posting lists is individually selectable.

### Claim 20 (depends on 19)

The processor-readable storage medium of claim 19, wherein determining compression settings to use during the next predetermined time of the predetermined times includes determining, for each posting list of the plurality of posting lists, compression settings to use for that posting list during the next predetermined time of the predetermined times.
