# US 2024/0202244 A1 · Optimizing text filtering queries on graph data

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

- Number: US 2024/0202244 A1
- Document ID: US20240202244A1
- Status: Published application
- Kind: A1
- Application number: 18/542,207
- Filed: 2023-12-15
- Published: 2024-06-20
- Earliest claimed: 2022-12-15
- Assignees: Dassault Systemes
- Applicants: Dassault Systemes
- Inventors: François DAVIAU
- Web page: https://patentgrep.com/patent/US20240202244A1

## CPC

- G06F 16/319: {Inverted lists}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 3/064: {Management of blocks}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2453: Query optimisation
- G06F 16/9035: Filtering based on additional data, e.g. user or group profiles
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method for updating one or more inversed lists of a read/write graph database, each inversed list being associated with a trigram comprised in a literal value. The method including obtaining the dictionary encoder including a set of literal values and a set of IDs, each literal value being associated with an ID. The method further includes, for each literal value, identifying trigrams composing the literal value. The method further includes, for each identified trigram, and in a first data structure, updating a header of the inversed list associated with the identified trigram, and updating a designated block which includes a representation of the ID of the literal value including the trigram, thereby updating the inversed list associated to the identified trigram.

## Claims

### Claim 1

A computer-implemented method for updating one or more inversed lists of a read/write graph database, each inversed list being associated with a trigram comprised in a literal value, the method comprising:
obtaining a dictionary encoder including a set of literal values and a set of IDs, each literal value being associated with an ID; and
for each literal value:
identifying trigrams composing the literal value; and
for each identified trigram, and in a first data structure:
updating a header of the inversed list associated with the identified trigram, and
updating a designated block which includes a representation of the ID of the literal value having the trigram, thereby updating the inversed list associated to the identified trigram.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1 further comprising, upon meeting a criterion:
updating a representation of the ID of the literal value in a second data structure, the second data structure being associated with the header; and
initializing the designated block.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein the criterion is met when the designated block is full.

### Claim 4 (depends on 2)

The computer-implemented method of claim 2, wherein, the second data structure is a tree, and the method further comprises, upon the updating of the representation of the ID of the literal value in a second data structure:
updating a root address of the tree in the header.

### Claim 5 (depends on 2)

The computer-implemented method of claim 2, wherein the second data structure is a tree, the updated representation of the ID of the literal value in the second data structure comprising:
one or more blocks, each block being a set of eight 32-bit words.

### Claim 6 (depends on 1)

The computer-implemented method of claim 1, wherein the first data structure is any associative data structure.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the first data structure is a B+Tree, and
wherein the updating of a representation of the ID of the literal value comprises:
updating a reference of the ID in an internal node of the B+Tree, and
updating the ID in a leaf of the B+Tree.

### Claim 8 (depends on 1)

The computer-implemented method of claim 1, wherein the designated block of the first data structure is a set of eight 32-bit words.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, wherein each of the set of eight 32-bit words is configured according to one of following patterns:
16×2 bits integers,
8×3 bits then 2×4 bits,
2×4 bits then 8×3 bits,
8×4 bits,
4×5 bits then 2×6 bits,
2×6 bits then 4×5 bits,
3×6 bits then 2×7 bits,
2×7 bits then 3×6 bits,
4×8 bits,
1×10 bits then 2×11 bits,
2×11 bits then 1×10 bits,
1×8 bits then 1×24 bits,
2×16 bits,
1×24 bits then 1×8 bits, or
1×32 bits.

### Claim 10 (depends on 9)

The computer-implemented method of claim 9, wherein a first word of the set includes data of one or more of following:
an indicator if the designated block is full or not,
an indicator of a next word to be filled, and/or
an indicator of a pattern for each word.

### Claim 11 (depends on 1)

The computer-implemented method of claim 1, wherein the representation of the ID of the literal value indicates a difference between:
a first ID of a first literal value including the identified trigram, and
a second ID of a second literal value including the identified trigram.

### Claim 12 (depends on 1)

A method of answering a query using the updated inversed lists according to the computer-implemented method of claim 1, the method comprising:
obtaining a query by a query engine, the query containing at least one filter for a literal value;
obtaining one or more updated inversed lists, the one or more obtained inversed lists being associated to respective one or more trigrams composing the literal value of the filter; and
answering the obtained query using a subset of the one or more obtained inversed lists.

### Claim 13 (depends on 12)

The method of claim 12, wherein the subset of the one more of the one or more obtained inversed lists are a subset of a minimal cardinality among the one or more obtained inversed lists.

### Claim 14

A non-transitory computer readable having stored thereon a computer program having instructions which, when executed by a computer, cause the computer to carry out the method of 1.

### Claim 15

A non-transitory computer readable having stored thereon a computer program having instructions which, when executed by a computer, cause the computer to carry out the method of 12.

### Claim 16

A read/write graph database comprising:
at least one inversed list, each inversed list of the database being associated with a trigram comprised in a literal value, the at least one inversed list of the database being updated by a processor being configured to update one or more inversed lists of a read/write graph database, each inversed list being associated with a trigram comprised in a literal value, the processor being configured to:
obtain a dictionary encoder including a set of literal values and a set of IDs, each literal value being associated with an ID; and
for each literal value:
identify trigrams composing the literal value; and
for each identified trigram, and in a first data structure:
update a header of the inversed list associated with the identified trigram, and
update a designated block which includes a representation of the ID of the literal value having the trigram, thereby updating the inversed list associated to the identified trigram.

### Claim 17 (depends on 3)

The computer-implemented method of claim 3, wherein, the second data structure is a tree, and the method further comprises, upon the updating of the representation of the ID of the literal value in a second data structure:
updating a root address of the tree in the header.

### Claim 18 (depends on 3)

The computer-implemented method of claim 3, wherein the second data structure is a tree, the updates representation of the ID of the literal value in the second data structure comprising:
one or more blocks, each block being a set of eight 32-bit words.

### Claim 19 (depends on 6)

The computer-implemented method of claim 6, wherein the first data structure is a tree.

### Claim 20

An apparatus for updating one or more inversed lists of a read/write graph database, each inversed list being associated with a trigram comprised in a literal value, the apparatus comprising:
processing circuitry configured to:
obtain a dictionary encoder including a set of literal values and a set of IDs, each literal value being associated with an ID; and
for each literal value:
identify trigrams composing the literal value; and
for each identified trigram, and in a first data structure:
update a header of the inversed list associated with the identified trigram, and
update a designated block which includes a representation of the ID of the literal value having the trigram, thereby updating the inversed list associated to the identified trigram.
