US 2021/0279282 A1 · EFFICIENT, IN-MEMORY, RELATIONAL REPRESENTATION FOR HETEROGENEOUS GRAPHS

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.

Claims20

Dependent claims

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.

8 more elements

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.

8 more elements

Dependencies are inferred from the claim text.

Efficient, in-memory, relational representation for heterogeneous graphs

Life of this patent

Efficient, in-memory, relational representation for heterogeneous graphs

Life of this patent

Abstract

Claims20