# US 2023/0418870 A1 · Adjacency structure for heterogeneous graph data

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

- Number: US 2023/0418870 A1
- Document ID: US20230418870A1
- Status: Published application
- Kind: A1
- Application number: 17/847,836
- Filed: 2022-06-23
- Published: 2023-12-28
- Earliest claimed: 2022-06-23
- Assignees: Sap SE
- Applicants: Sap SE
- Inventors: Matthias Hauck; Hannes Jakschitsch; Umang Rawat; Romans Kasperovics
- Web page: https://patentgrep.com/patent/US20230418870A1

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method may include generating, for a heterogeneous graph comprising a plurality of vertex tables and/or edge tables, an adjacency structure including a vertex adjacency structure specifying a plurality of neighboring vertices in the heterogeneous graph and an edge adjacency structure specifying a plurality of neighboring edges in the heterogeneous graph. A graph processing algorithm operating on the heterogeneous graph may be executed based on the adjacency structure. Related systems and computer program products are also provided.

## Claims

### Claim 1

A system, comprising:
at least one data processor; and
at least one memory storing instructions which, when executed by the at least one data processor, result in operations comprising:
generating, for a heterogeneous graph comprising a plurality of vertex tables and/or edge tables, an adjacency structure including a vertex adjacency structure specifying a plurality of neighboring vertices in the heterogeneous graph and an edge adjacency structure specifying a plurality of neighboring edges in the heterogeneous graph; and
executing, based at least on the adjacency structure, a graph processing algorithm operating on the heterogeneous graph.

### Claim 2 (depends on 1)

The system of claim 1, wherein the heterogeneous graph is associated with a first vertex table and a second vertex table, and wherein the heterogeneous graph is further associated with a set of vertex dictionaries comprising a first vertex dictionary associated with the first vertex table and a second vertex dictionary associated with the second vertex table.

### Claim 3 (depends on 2)

The system of claim 2, wherein the first vertex dictionary includes, for a first vertex in the first vertex table of the heterogeneous graph, a first local identifier that is unique across the first vertex dictionary and a first global identifier that is unique across the set of vertex dictionaries, and wherein the second vertex dictionary includes, for a second vertex in the second vertex table of the heterogeneous graph, a second local identifier that is unique across the second vertex dictionary and a second global identifier that is unique across the set of the vertex dictionaries.

### Claim 4 (depends on 3)

The system of claim 3, wherein the vertex adjacency list specifies the first vertex and the second vertex as neighboring vertices by at least identifying the first vertex based on the first global identifier and the second vertex based on the second global identifier.

### Claim 5 (depends on 1)

The system of claim 1, wherein the heterogeneous graph is associated with a first edge table and a second edge table, and wherein the heterogeneous graph is further associated with a set of edge dictionaries comprising a first edge dictionary associated with the first edge table and a second edge dictionary associated with the second edge table.

### Claim 6 (depends on 5)

The system of claim 5, wherein the first edge dictionary includes, for a first edge in the first edge table of the heterogeneous graph, a first local identifier that is unique across the first edge dictionary and a first global identifier that is unique across the set of edge dictionaries, and wherein the second edge dictionary includes, for a second edge in the second edge table of the heterogeneous graph, a second local identifier that is unique across the second edge dictionary and a second global identifier that is unique across the set of the edge dictionaries.

### Claim 7 (depends on 6)

The system of claim 6, wherein the edge adjacency list specifies the first edge and the second edge as neighboring edges by at least identifying the first edge based on the first global identifier and the second edge based on the second global identifier.

### Claim 8 (depends on 1)

The system of claim 1, wherein each vertex or edge in the heterogeneous graph is uniquely identified based on a label of a corresponding table and one or more key attributes.

### Claim 9 (depends on 1)

The system of claim 1, wherein the plurality of vertex tables and/or edge tables include an arbitrary quantity of vertex tables and/or edge tables.

### Claim 10 (depends on 1)

The system of claim 1, wherein the operations further comprise:
receiving an external key identifying a vertex or an edge in the heterogeneous graph, the external key including a key value and a label;
determining that the label exists within the heterogeneous graph based at least on the label being associated to a vertex table or an edge table comprising the heterogeneous graph;
determining that a key type of the key value is correct for the label; and
upon determining that the key value exists within the vertex table or edge table associated with the label, retrieving, based at least on a dictionary of the vertex table or edge table associated with the label, an internal key corresponding to the external key.

### Claim 11 (depends on 1)

The system of claim 1, wherein the operations further comprise:
receiving an internal key identifying a vertex or an edge in the heterogeneous graph;
identifying, based at least on a prefix sum list of a plurality of partitions comprising the adjacency structure, a label of a vertex table or an edge table and an internal identifier corresponding to the internal key; and
identifying, within a dictionary of the vertex table or the edge table having the label, external key corresponding to the internal identifier.

### Claim 12 (depends on 1)

The system of claim 1, wherein each of the vertex adjacency structure and the edge adjacency structure comprise a list or a matrix.

### Claim 13 (depends on 1)

The system of claim 1, wherein the plurality of vertex tables and/or edge tables comprises one or more documents.

### Claim 14 (depends on 1)

The system of claim 1, wherein the graph processing algorithm includes one or more graph processing functions including subgraph, inverse graph, in-degree, out-degree, incoming edges, outgoing edges, neighbors, is-reachable, shortest path, shortest path one to all, k shortest paths, strongly connected components, depth first traversal, and breadth first traversal.

### Claim 15

A computer-implemented method, comprising:
generating, for a heterogeneous graph comprising a plurality of vertex tables and/or edge tables, an adjacency structure including a vertex adjacency structure specifying a plurality of neighboring vertices in the heterogeneous graph and an edge adjacency structure specifying a plurality of neighboring edges in the heterogeneous graph; and
executing, based at least on the adjacency structure, a graph processing algorithm operating on the heterogeneous graph.

### Claim 16 (depends on 15)

The method of claim 15, wherein the heterogeneous graph is associated with a first vertex table and a second vertex table, and wherein the heterogeneous graph is further associated with a set of vertex dictionaries comprising a first vertex dictionary associated with the first vertex table and a second vertex dictionary associated with the second vertex table.

### Claim 17 (depends on 16)

The method of claim 16, wherein the first vertex dictionary includes, for a first vertex in the first vertex table of the heterogeneous graph, a first local identifier that is unique across the first vertex dictionary and a first global identifier that is unique across the set of vertex dictionaries, wherein the second vertex dictionary includes, for a second vertex in the second vertex table of the heterogeneous graph, a second local identifier that is unique across the second vertex dictionary and a second global identifier that is unique across the set of the vertex dictionaries, and wherein the vertex adjacency list specifies the first vertex and the second vertex as neighboring vertices by at least identifying the first vertex based on the first global identifier and the second vertex based on the second global identifier.

### Claim 18 (depends on 15)

The method of claim 15, wherein the heterogeneous graph is associated with a first edge table and a second edge table, and wherein the heterogeneous graph is further associated with a set of edge dictionaries comprising a first edge dictionary associated with the first edge table and a second edge dictionary associated with the second edge table.

### Claim 19 (depends on 18)

The method of claim 18, wherein the first edge dictionary includes, for a first edge in the first edge table of the heterogeneous graph, a first local identifier that is unique across the first edge dictionary and a first global identifier that is unique across the set of edge dictionaries, wherein the second edge dictionary includes, for a second edge in the second edge table of the heterogeneous graph, a second local identifier that is unique across the second edge dictionary and a second global identifier that is unique across the set of the edge dictionaries, and wherein the edge adjacency list specifies the first edge and the second edge as neighboring edges by at least identifying the first edge based on the first global identifier and the second edge based on the second global identifier.

### Claim 20

A non-transitory computer readable medium storing instructions, which when executed by at least one data processor, result in operations comprising:
generating, for a heterogeneous graph comprising a plurality of vertex tables and/or edge tables, an adjacency structure including a vertex adjacency structure specifying a plurality of neighboring vertices in the heterogeneous graph and an edge adjacency structure specifying a plurality of neighboring edges in the heterogeneous graph; and
executing, based at least on the adjacency structure, a graph processing algorithm operating on the heterogeneous graph.
