# US 2021/0279282 A1 · Efficient, in-memory, relational representation for heterogeneous graphs

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

- Number: US 2021/0279282 A1
- Document ID: US20210279282A1
- Status: Published application
- Kind: A1
- Application number: 17/330,046
- Filed: 2021-05-25
- Published: 2021-09-09
- Earliest claimed: 2018-04-18
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: DAMIEN HILLOULIN; DAVIDE BARTOLINI; OSKAR VAN REST; Alexander Weld; Sungpack Hong; Hassan Chafi
- Web page: https://patentgrep.com/patent/US20210279282A1

## CPC

- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/288: {Entity relationship models}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques are provided herein for efficient representation of heterogeneous graphs in memory. In an embodiment, vertices and edges of the graph are segregated by type. Each property of a type of vertex or edge has values stored in a respective vector. Directed or undirected edges of a same type are stored in compressed sparse row (CSR) format. The CSR format is more or less repeated for edge traversal in either forward or reverse direction. An edge map translates edge offsets obtained from traversal in the reverse direction for use with data structures that expect edge offsets in the forward direction. Subsequent filtration and/or traversal by type or property of vertex or edge entails minimal data access and maximal data locality, thereby increasing efficient use of the graph.

## Claims

### Claim 1

A method, performed by one or more computers, and comprising:
for each record type of a plurality of record types from a data source:
associating the record type with a distinct vertex type in a graph being constructed in memory;
for each data field of a plurality of data fields in the record type, associating the data field with: the distinct vertex type, and a vertex property vector that resides in the memory; and
for each record of a plurality of records of the record type:
creating, in the graph, a vertex, which represents the record, as an instance of the distinct vertex type of the record type;
associating the vertex with a unique offset; and
for each data field of the plurality of data fields, storing a value from the data field of the record into the vertex property vector, which is associated with the data field, at the unique offset of the vertex;
reading the graph by accessing the vertex property vector of a distinct vertex type.

### Claim 2 (depends on 1)

The method of claim 1 wherein said reading comprises executing a query of the graph by:
detecting one or more vertex types are relevant to the query; and
not accessing vertex property vectors of data fields of a particular record type unless the particular record type is associated with a vertex type of said one or more vertex types.

### Claim 3 (depends on 1)

The method of claim 1 wherein:
the method further comprises associating said distinct vertex type with a plurality of distinct edge types;
the reading of the graph comprises reading at least one instance of at least one edge type of the plurality of distinct edge types.

### Claim 4 (depends on 1)

The method of claim 1 further comprising:
assigning a unique serial number to said distinct vertex type;
identifying a particular vertex that is an instance of a particular vertex type by an identifying pair that comprises: the unique serial number of the particular vertex type, and said unique offset of the particular vertex.

### Claim 5 (depends on 4)

The method of claim 4 wherein said identifying pair consists of at most 128 bits.

### Claim 6 (depends on 4)

The method of claim 4 wherein said identifying pair consists of at most 64 bits.

### Claim 7 (depends on 4)

The method of claim 4 wherein the unique serial number of the particular vertex type and said unique offset of the particular vertex are bit packed within said identifying pair.

### Claim 8 (depends on 1)

The method of claim 1 wherein:
the data source comprises a relational database;
the record type comprises a table in the relational database;
the record comprises a row in the table;
the data field comprises a column in the table.

### Claim 9

One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
for each record type of a plurality of record types from a data source:
associating the record type with a distinct vertex type in a graph being constructed in memory;
for each data field of a plurality of data fields in the record type, associating the data field with: the distinct vertex type, and a vertex property vector that resides in the memory; and
for each record of a plurality of records of the record type:
creating, in the graph, a vertex, which represents the record, as an instance of the distinct vertex type of the record type;
associating the vertex with a unique offset; and
for each data field of the plurality of data fields, storing a value from the data field of the record into the vertex property vector, which is associated with the data field, at the unique offset of the vertex;
reading of the graph by accessing the vertex property vector of a distinct vertex type.

### Claim 10 (depends on 9)

The one or more non-transitory computer-readable media of claim 9 wherein said reading comprises executing a query of the graph by:
detecting one or more vertex types are relevant to the query; and
not accessing vertex property vectors of data fields of a particular record type unless the particular record type is associated with a vertex type of said one or more vertex types.

### Claim 11 (depends on 9)

The one or more non-transitory computer-readable media of claim 9 wherein:
the instructions further cause associating said distinct vertex type with a plurality of distinct edge types;
the reading of the graph comprises reading at least one instance of at least one edge type of the plurality of distinct edge types.

### Claim 12 (depends on 9)

The one or more non-transitory computer-readable media of claim 9 wherein the instructions further cause:
assigning a unique serial number to said distinct vertex type;
identifying a particular vertex that is an instance of a particular vertex type by an identifying pair that comprises: the unique serial number of the particular vertex type, and said unique offset of the particular vertex.

### Claim 13 (depends on 12)

The one or more non-transitory computer-readable media of claim 12 wherein said identifying pair consists of at most 128 bits.

### Claim 14 (depends on 12)

The one or more non-transitory computer-readable media of claim 12 wherein said identifying pair consists of at most 64 bits.

### Claim 15 (depends on 12)

The one or more non-transitory computer-readable media of claim 12 wherein the unique serial number of the particular vertex type and said unique offset of the particular vertex are bit packed within said identifying pair.

### Claim 16 (depends on 9)

The one or more non-transitory computer-readable media of claim 9 wherein:
the data source comprises a relational database;
the record type comprises a table in the relational database;
the record comprises a row in the table;
the data field comprises a column in the table.

### Claim 17

A computer configured to:
for each record type of a plurality of record types from a data source:
associate the record type with a distinct vertex type in a graph being constructed in memory;
for each data field of a plurality of data fields in the record type, associate the data field with: the distinct vertex type, and a vertex property vector that resides in the memory; and
for each record of a plurality of records of the record type:
create, in the graph, a vertex, which represents the record, as an instance of the distinct vertex type of the record type;
associate the vertex with a unique offset; and
for each data field of the plurality of data fields, store a value from the data field of the record into the vertex property vector, which is associated with the data field, at the unique offset of the vertex;
read the graph by accessing the vertex property vector of a distinct vertex type.

### Claim 18 (depends on 17)

The computer of claim 17 wherein said read comprises execute a query of the graph by:
detecting one or more vertex types are relevant to the query; and
not accessing vertex property vectors of data fields of a particular record type unless the particular record type is associated with a vertex type of said one or more vertex types.

### Claim 19 (depends on 17)

The computer of claim 17 wherein:
the computer is further configured to associate said distinct vertex type with a plurality of distinct edge types;
the reading of the graph comprises reading at least one instance of at least one edge type of the plurality of distinct edge types.

### Claim 20 (depends on 17)

The computer of claim 17 wherein the computer is further configured to:
assign a unique serial number to said distinct vertex type;
identify a particular vertex that is an instance of a particular vertex type by an identifying pair that comprises: the unique serial number of the particular vertex type, and said unique offset of the particular vertex.
