In-memory graph analytics system that allows memory and performance trade-off between graph mutation and graph traversal

Patent metadata

Field	Value
Publication number	US-10235474-B2
Application number	US-201715443327-A
Country	US
Kind code	B2
Filing date	Feb 27, 2017
Priority date	Feb 27, 2017
Publication date	Mar 19, 2019
Grant date	Mar 19, 2019

Abstract

Techniques herein are for navigation data structures for graph traversal. In an embodiment, navigation data structures that a computer stores include: a source vertex array of vertices; a neighbor array of dense identifiers of target vertices terminating edges; a bidirectional map associating, for each vertex, a sparse identifier of the vertex with a dense identifier of the vertex; and a vertex array containing, when a dense identifier of a source vertex is used as an offset, a pair of offsets defining an offset range, for use with the neighbor array. The source vertex array, using the dense identifier of a particular vertex as an offset, contains an offset, into a neighbor array, of a target vertex terminating an edge originating at the particular vertex. The neighbor array contiguously stores dense identifiers of target vertices terminating edges originating from a same source vertex.

First claim

What is claimed is:

1. A method comprising:
storing a source vertex array of vertices of a directed graph, wherein:
each vertex of the directed graph is identifiable by each of: a dense identifier comprising an offset of the vertex within the source vertex array, and a sparse identifier;
a particular vertex of the directed graph originates one or more edges;
each edge of the particular vertex terminates at a respective target vertex;
the source vertex array, using the dense identifier of a particular vertex as an offset, contains an offset, into a neighbor array, of a target vertex that terminates an edge that originates at the particular vertex; and
the neighbor array contains dense identifiers of target vertices that terminate edges of the directed graph, wherein dense identifiers of the target vertices that terminate edges that originate from a same source vertex are stored contiguously in the neighbor array, wherein the neighbor array is sorted by the dense identifier of the source vertex of the edge that terminates the target vertex;

storing a bidirectional map that, for each vertex of the directed graph, associates the sparse identifier of the vertex with the dense identifier of the vertex;
storing a vertex array that, when a dense identifier of a source vertex is used as an offset, contains a pair of offsets that define a range of offsets, for use with the neighbor array.

2. The method of claim 1 further comprising:
buffering a plurality of change descriptors that describe changes to the directed graph until an amount of change descriptors exceeds a first threshold;
when the first threshold is exceeded, processing each change descriptor of the plurality of change descriptors.

3. The method of claim 2 wherein:
the method further comprises storing a materialized array of sparse identifiers of target vertices that terminate edges of the directed graph, wherein sparse identifiers of the target vertices that terminate edges that originate from a same source vertex are stored contiguously in the materialized array, wherein the materialized array is sorted by the dense identifier of the source vertex of the edge that terminates the target vertex;
the plurality of change descriptors comprises a particular change descriptor that affects a particular edge that originates at a particular vertex;
processing the particular change descriptor comprises inserting, into the materialized array, the sparse identifier of the target vertex of the particular edge.

4. The method of claim 3 wherein:
the method further comprises detecting that the particular vertex should be fully materialized;
inserting, into the materialized array, the sparse identifier of the target vertex of the particular edge comprises:
inserting, into the materialized array, sparse identifiers of target vertices of all edges that originate at the particular vertex;
marking, using the dense identifier of the particular vertex as an offset of a particular pair within the vertex array, the lesser offset of the particular pair by at least one of: setting the high order bit, or negating the sign.

5. The method of claim 3 wherein the method further comprises:
detecting that the particular vertex should not be fully materialized;
marking, using the dense identifier of the particular vertex as an offset of a particular pair within the vertex array, both offsets of the particular pair by at least one of:
setting the high order bit, or negating the sign.

6. The method of claim 3 wherein:
the particular change descriptor specifies removing the particular edge;
processing the particular change descriptor comprises:
identifying, using the dense identifier of the particular vertex as an offset of a particular pair within the vertex array, a subarray within the materialized array;
marking, within the subarray, the sparse identifier of the target vertex of the particular edge by at least one of: setting the high order bit, or negating the sign.

7. The method of claim 3 wherein the method further comprises storing:
a reverse source vertex array of vertices of a directed graph, wherein:
each edge of the particular vertex originates at a respective source vertex;
the reverse source vertex array, using the dense identifier of the particular vertex as an offset, contains an offset, into a second neighbor array, of a source vertex that originates an edge that terminates at the particular vertex; and
the second neighbor array contains dense identifiers of source vertices that originate edges of the directed graph, wherein dense identifiers of the source vertices that originate edges that terminate at a same target vertex are stored contiguously in the second neighbor array, wherein the second neighbor array is sorted by the dense identifier of the target vertex of the edge that originates the source vertex, wherein the second neighbor array does not reflect the plurality of change descriptors;

a second vertex array that, when a dense identifier of a target vertex is used as an offset, contains a pair of offsets that define a range of offsets, for use with the second neighbor array.

8. The method of claim 3 wherein:
the method further comprises storing:
one or more edge property arrays that store unchanged values of edge properties, and
one or more edge property change arrays that store changed values of edge properties;

an offset into each edge property array of the one or more edge property arrays for a particular edge is a same offset into the neighbor array for the particular edge;
an offset into each edge property change array of the one or more edge property arrays for a particular edge is a same offset into the materialized array for the particular edge.

9. The method of claim 8 wherein:
edge property values are accessible by forward traversal and backward traversal;
edge property values are stored in memory essentially only once.

10. The method of claim 3 further comprising assigning each edge of the directed graph a unique integer that is based on an offset into one of: the neighbor array or the materialized array.

11. One or more non-transient computer readable media storing instructions that, when executed by one or more processors, cause:
storing a source vertex array of vertices of a directed graph, wherein:
each vertex of the directed graph is identifiable by each of: a dense identifier comprising an offset of the vertex within the source vertex array, and a sparse identifier;
a particular vertex of the directed graph originates one or more edges;
each edge of the particular vertex terminates at a respective target vertex;
the source vertex array, using the dense identifier of a particular vertex as an offset, contains an offset, into a neighbor array, of a target vertex that terminates an edge that originates at the particular vertex; and
the neighbor array contains dense identifiers of target vertices that terminate edges of the directed graph, wherein dense identifiers of the target vertices that terminate edges that originate from a same source vertex are stored contiguously in the neighbor array, wherein the neighbor array is sorted by the dense identifier of the source vertex of the edge that terminates the target vertex;

storing a bidirectional map that, for each vertex of the directed graph, associates the sparse identifier of the vertex with the dense identifier of the vertex;
storing a vertex array that, when a dense identifier of a source vertex is used as an offset, contains a pair of offsets that define a range of offsets, for use with the neighbor array.

12. The one or more non-transient computer readable media of claim 11 wherein the i

Assignees

• Oracle Int Corp

Inventors

• Haubenschild Michael
• Hong Sungpack
• Chafi Hassan
• Schmid Korbinian
• Sevenich Martin
• Weld Alexander

Classifications

• G06F17/30958 Primary

  Physics · mapped topic

• G06F17/30477

  Physics · mapped topic

• G06F16/28

  Databases characterised by their database models, e.g. relational or object models · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title