Granted Patent B2

US 12,724,823 · App. 17/194,165 · Granted Sep 1, 2026

Inventors: Damien Hilloulin (Zurich, CH); Vasileios Trigonakis (Zurich, CH); Alexander Weld (Mountain View, CA); Valentin Venzin (Zurich, CH); Sungpack Hong (Palo Alto, CA); Hassan Chafi (San Mateo, CA)

Assignee: Oracle International Corporation

G06F16/9024G06F16/2282

Abstract

Claims (78)

1 . A method comprising:

in memory of one or more computers, storing an in-memory bi-directional representation for a graph comprising a plurality of vertices connected by a plurality of edges, wherein each of the plurality of edges is directed from a respective source vertex to a respective destination vertex;

wherein storing the in-memory bi-directional representation for the graph includes:

storing a forward representation of the graph that comprises:

an edge array that is segmented, wherein each edge array index of the edge array holds a vertex id of a destination vertex of a respective edge that corresponds to a respective edge array index;

a begin array that is segmented, wherein each begin array index of the begin array is associated with a respective source vertex identified by a respective begin array index and holds an edge array index at which a respective source vertex edge list of the respective source vertex is stored sequentially within the edge array;

storing a reverse representation of the graph that comprises:

a reverse edge array that is segmented, wherein each reverse edge array index of the reverse edge array holds a vertex id of a source vertex of a respective edge that corresponds to the respective reverse edge array index;

a reverse begin array that is segmented, wherein each reverse begin array index of the reverse begin array is associated with a respective destination vertex identified by the respective reverse begin array index and holds a reverse edge array index at which a respective destination vertex edge list of the respective destination vertex is stored sequentially within the reverse edge array;

an edge offset array that is segmented, wherein each edge offset array index of the edge offset array corresponds to a particular reverse edge array index and a particular edge and a particular source vertex of the particular reverse edge array index, wherein said particular source vertex has a particular source vertex id, wherein said each edge offset array index holds an offset for a particular edge within the edge array, wherein a sum of the offset and the offset held in the begin array at the begin array index that is equal to the particular source vertex id equals the edge array index of the particular edge;

wherein:

the plurality of vertices are stored in a plurality of tables that include at least two vertex tables, and

each property of said at least two vertex tables is associated with an array with delta logs, the array with delta logs comprising (1) a consolidated values array storing values associated with a consolidated version of the vertex table (2) a delta log data structure storing changes compared to the consolidated values array; and

for a new snapshot of the graph, updating said graph with graph changes to said graph, wherein said updating includes:

for each property of said at least two vertex tables that has modifications included in said changes generating a new array of delta logs based on a previous respective array of delta logs of said each property; and

for each property of said at least two vertex tables without modifications included in said changes, reusing the respective array of delta logs of said each property for said new snapshot.

2 . The method of claim 1 , wherein the plurality of vertices and the plurality of edges are stored in a plurality of tables that includes at least two vertex tables and at least one edge table, wherein each of the at least two vertex tables stores the plurality of vertices of a certain type with specific sets of properties, wherein each of the at least one edge table stores the plurality of edges of a certain type with specific sets of properties.

3 . The method of claim 1 , wherein for each property of said at least two vertex tables, data structures of the respective array with delta logs of said each property are segmented according to a fixed size, wherein one or more segments are compacted when a consolidation threshold is satisfied.

4 . The method of claim 1 , wherein each property of an edge table for the graph is associated with a list-array with delta logs, wherein the list-array with delta logs comprises:

a consolidated lists array storing lists associated with a consolidated version of the edge table;

a consolidated list begins array storing, for each index of the consolidated list begins array, a start index of a corresponding list in the consolidated lists array;

a delta log data structure comprising:

a delta lists array storing content of modified or newly added lists;

a list positions data structure storing, for each index of the list positions data structure, a delta lists array index and a length of a particular list.

5 . The method of claim 4 , wherein data structures of the list-array with delta logs are segmented in per-vertex segments, wherein one or more segments are compacted when a consolidation threshold is satisfied.

6 . The method of claim 1 , wherein the edge array is a logical representation of a list-array with delta logs, wherein each of the begin array and the reverse begin array is associated with a checkpoint array and a difference array, wherein the difference array is logical representation of a block-array with delta logs.

7 . The method of claim 6 , wherein data structures of the block-array with delta logs are segmented in per-vertex segments, wherein one or more segments are compacted when a consolidation threshold is satisfied.

8 . The method of claim 1 , further comprising for each vertex table, for the graph, that contains one or more vertex changes to the graph:

if the one or more vertex changes include vertex deletions, allocating a bit array for a corresponding vertex table to indicate deleted vertices;

if the one or more vertex changes include vertex additions, transforming as many of the vertex additions into vertex compensations and assigning new vertex indices to any remaining vertex additions that are not transformed;

if the one or more vertex changes include vertex property modifications, for each property associated with the vertex property modifications, creating a new array of delta logs based on a previous array of delta logs, wherein the vertex property modifications are applied to a delta log data structure of the new array of delta logs.

9 . The method of claim 1 , further comprising for each edge table, for the graph, that contains one or more edge changes to the graph:

if the one or more edge changes include topological edge modifications,

creating a new begin array and a new reverse begin array, comprising for each of the new begin array and the new reverse begin array:

determining a number of edges for each source vertex of the plurality of vertices and for each destination vertex of the plurality of vertices;

creating a new checkpoint array and a new difference array based on the determination;

updating the edge array, comprising merging delta logs of a previous edge array with the topological edge modifications;

updating the edge offset array based on the topological edge modifications;

if the one or more edge changes include edge property modifications, for each property associated with the edge property modifications, creating a new delta log data structure based on a previous delta log data structure, wherein the edge property modifications are applied to the new delta log data structure.

10 . One or more non-transitory computer-readable storage media storing sequences of instructions which, when executed by one or more processors, cause:

in memory of one or more computers, storing an in-memory bi-directional representation for a graph comprising a plurality of vertices connected by a plurality of edges, wherein each of the plurality of edges is directed from a respective source vertex to a respective destination vertex;

wherein storing the in-memory bi-directional representation for the graph includes:

storing a forward representation of the graph that comprises:

an edge array that is segmented, wherein each edge array index of the edge array holds a vertex id of a destination vertex of a respective edge that corresponds to a respective edge array index;

a begin array that is segmented, wherein each begin array index of the begin array is associated with a respective source vertex identified by a respective begin array index and holds an edge array index at which a respective source vertex edge list of the respective source vertex is stored sequentially within the edge array;

storing a reverse representation of the graph that comprises:

a reverse edge array that is segmented, wherein each reverse edge array index of the reverse edge array holds a vertex id of a source vertex of a respective edge that corresponds to the respective reverse edge array index;

a reverse begin array that is segmented, wherein each reverse begin array index of the reverse begin array is associated with a respective destination vertex identified by the respective reverse begin array index and holds a reverse edge array index at which a respective destination vertex edge list of the respective destination vertex is stored sequentially within the reverse edge array;

an edge offset array that is segmented, wherein each edge offset array index of the edge offset array corresponds to a particular reverse edge array index and a particular edge and a particular source vertex of the particular reverse edge array index, wherein said particular source vertex has a particular source vertex id, wherein said each edge offset array index holds an offset for a particular edge within the edge array, wherein a sum of the offset and the offset held in the begin array at the begin array index that is equal to the particular source vertex id equals the edge array index of the particular edge;

wherein:

the plurality of vertices are stored in a plurality of tables that include at least two vertex tables, and

each property of said at least two vertex tables is associated with an array with delta logs, the array with delta logs comprising (1) a consolidated values array storing values associated with a consolidated version of the vertex table (2) a delta log data structure storing changes compared to the consolidated values array; and

for a new snapshot of the graph, updating said graph with graph changes to said graph, wherein said updating includes;

for each property of said at least two vertex tables that has modifications included in said changes generating a new array of delta logs based on a previous respective array of delta logs of said each property; and

for each property of said at least two vertex tables without modifications included in said changes, reusing the respective array of delta logs of said each property for said new snapshot.

11 . The one or more non-transitory computer-readable storage media of claim 10 , wherein the plurality of vertices and the plurality of edges are stored in a plurality of tables that includes at least two vertex tables and at least one edge table, wherein each of the at least two vertex tables stores the plurality of vertices of a certain type with specific sets of properties, wherein each of the at least one edge table stores the plurality of edges of a certain type with specific sets of properties.

12 . The one or more non-transitory computer-readable storage media of claim 10 , wherein for each property of said at least two vertex tables, data structures of the respective array with delta logs of said each property are segmented according to a fixed size, wherein one or more segments are compacted when a consolidation threshold is satisfied.

13 . The one or more non-transitory computer-readable storage media of claim 10 , wherein each property of an edge table for the graph is associated with a list-array with delta logs, wherein the list-array with delta logs comprises:

a consolidated lists array storing lists associated with a consolidated version of the edge table;

a consolidated list begins array storing, for each index of the consolidated list begins array, a start index of a corresponding list in the consolidated lists array;

a delta log data structure comprising:

a delta lists array storing content of modified or newly added lists;

a list positions data structure storing, for each index of the list positions data structure, a delta lists array index and a length of a particular list.

14 . The one or more non-transitory computer-readable storage media of claim 13 , wherein data structures of the list-array with delta logs are segmented in per-vertex segments, wherein one or more segments are compacted when a consolidation threshold is satisfied.

15 . The one or more non-transitory computer-readable storage media of claim 10 , wherein the edge array is a logical representation of a list-array with delta logs, wherein each of the begin array and the reverse begin array is associated with a checkpoint array and a difference array, wherein the difference array is logical representation of a block-array with delta logs.

16 . The one or more non-transitory computer-readable storage media of claim 15 , wherein data structures of the block-array with delta logs are segmented in per-vertex segments, wherein one or more segments are compacted when a consolidation threshold is satisfied.

17 . The one or more non-transitory computer-readable storage media of claim 10 , wherein the sequences of instructions which, when executed by the one or more processors, further cause, for each vertex table, for the graph, that contains one or more vertex changes to the graph:

if the one or more vertex changes include vertex deletions, allocating a bit array for a corresponding vertex table to indicate deleted vertices;

if the one or more vertex changes include vertex additions, transforming as many of the vertex additions into vertex compensations and assigning new vertex indices to any remaining vertex additions that are not transformed;

if the one or more vertex changes include vertex property modifications, for each property associated with the vertex property modifications, creating a new array of delta logs based on a previous array of delta logs, wherein the vertex property modifications are applied to a delta log data structure of the new array of delta logs.

18 . The one or more non-transitory computer-readable storage media of claim 10 , wherein the sequences of instructions which, when executed by the one or more processors, further cause, for each edge table, for the graph, that contains one or more edge changes to the graph:

if the one or more edge changes include topological edge modifications,

creating a new begin array and a new reverse begin array, comprising for each of the new begin array and the new reverse begin array:

determining a number of edges for each source vertex of the plurality of vertices and for each destination vertex of the plurality of vertices;

creating a new checkpoint array and a new difference array based on the determination;

updating the edge array, comprising merging delta logs of a previous edge array with the topological edge modifications;

updating the edge offset array based on the topological edge modifications;

if the one or more edge changes include edge property modifications, for each property associated with the edge property modifications, creating a new delta log data structure based on a previous delta log data structure, wherein the edge property modifications are applied to the new delta log data structure.

Assignments (1)

Continuity (1)

References Cited (150)