Graph processing using a mutable multilevel graph representation

Patent metadata

Field	Value
Publication number	US-9734607-B2
Application number	US-201414483052-A
Country	US
Kind code	B2
Filing date	Sep 10, 2014
Priority date	Sep 10, 2014
Publication date	Aug 15, 2017
Grant date	Aug 15, 2017

Abstract

A mutable multilevel data structure representing a graph structure may include multiple read-only levels and a single writable level. Each read-only level may include a vertex table (with references to edge tables on the same level or a different level containing elements of adjacency lists for some vertices) and an edge table (with elements of adjacency lists that changed since the previous read-only level). A hybrid variant may switch between a performance-optimized variant (whose edge tables include complete adjacency lists for vertices whose edge sets were modified) and a space-optimized variant (whose edge tables include only newly added adjacency list elements). The vertex tables and/or the writable level may be implemented using copy-on-write arrays, each including an indirection table and multiple fixed-sized data pages. Computations may be run on the read-only levels or on the writable level and read-only levels.

First claim

What is claimed:

1. A system, comprising:
one or more processors; and
a memory coupled to the one or more processors;
wherein the memory stores at least a portion of a mutable multilevel data structure that represents a graph structure;
wherein the memory further stores program instructions that when executed on the one or more processors cause the one or more processors to implement a graph processing module;
wherein in response to receiving a request to perform a computation on the graph structure, the graph processing module is configured to reconstruct an adjacency list for a given vertex of the graph structure from information stored in the mutable multilevel data structure that represents the graph structure; and
wherein the mutable multilevel data structure comprises two or more read-only data structures that collectively represent a read-only snapshot of the graph structure, wherein one of the two or more read-only data structures at a given level of the mutable multilevel data structure comprises a consistent compressed sparse row representation of the graph structure at a given point in time, wherein each of the two or more read-only data structures is located at a respective level in the mutable multilevel data structure, wherein each of the two or more read-only data structures comprises a respective vertex table and edge table, and wherein another one of the two or more read-only data structures at another level of the mutable multilevel data structure includes a vertex table with one or more references to an edge table in the one read-only data structure at the given level.

2. The system of claim 1 , wherein to reconstruct the adjacency list for the given vertex, the graph processing module is configured to:
traverse one or more of the two or more read-only data structures to obtain elements of the adjacency list for the given vertex; and
add the obtained elements to the adjacency list for the given vertex.

3. The system of claim 1 , wherein the mutable multilevel data structure further comprises a single writeable data structure comprising information reflecting changes made to the graph structure that are not reflected in the two or more read-only data structures, wherein the single writable data structure and the two or more read-only data structures collectively represent a current state of the graph structure.

4. The system of claim 3 , wherein to reconstruct the adjacency list for the given vertex, the graph processing module is further configured to:
traverse the single writeable data structure to obtain one or more additional elements of the adjacency list for the given vertex; and
add the additional obtained elements to the adjacency list for the given vertex.

5. The system of claim 3 , wherein the single writable data structure is located at a level in the mutable multilevel data structure other than the respective levels at which the two or more read-only data structures are located, wherein the single writable data structure includes a vertex table comprising a direct or indirect reference to one or more elements of the adjacency list for the given vertex, and wherein the vertex table of the other one of the two or more read-only data structures at the other level of the mutable multilevel data structure further includes one or more references to an edge table in the other one of the two or more read-only data structures at the other level.

6. The system of claim 3 ,
wherein the single writable data structure comprises information about one or more elements of the adjacency list for the given vertex;
wherein the graph processing module is further configured to create a new read-only data structure at a new level of the mutable multilevel data structure dependent on the information in the single writable data structure about the one or more elements of the adjacency list for the given vertex; and
wherein to create the new read-only data structure, the graph processing module is configured to:
copy to the new read-only data structure, for each vertex in the graph structure for which there is information about one or more elements of the adjacency list for the vertex in the single writeable data structure, including the given vertex, the entire adjacency list for the vertex; or
copy to the new read-only data structure, for each vertex in the graph structure for which there is information about one or more elements of the adjacency list for the vertex in the single writeable data structure, including the given vertex, only the elements of the adjacency list for the vertex that have been modified since the time that a most-recently created read-only data structure in the mutable multilevel data structure was created.

7. The system of claim 3 ,
wherein the single writeable data structure includes a vertex table comprising a direct or indirect reference to one or more elements of the adjacency list for the given vertex;
wherein to perform the computation on the graph structure, the graph processing module is further configured to create a new read-only data structure at a new level of the mutable multilevel data structure; and
wherein to create the new read-only data structure, the graph processing module is configured to:
determine, for each vertex in the graph structure for which there is information about one or more elements of the adjacency list for the vertex in the single writeable data structure, including the given vertex, whether to perform an operation to copy the entire adjacency list for the vertex to the new read-only data structure or an operation to copy to the new read-only data structure only the elements of the adjacency list for the vertex that have been modified since the time that a most-recently created read-only data structure in the mutable multilevel data structure was created; and
perform the determined copy operation;
wherein the determination is dependent on one or more of:
a configuration parameter value indicating selection of one of two or more supported copy policies; or
a comparison between a degree of the vertex and a pre-determined degree threshold value.

8. The system of claim 1 , wherein to reconstruct the adjacency list for the given vertex, the graph processing module is configured to:
obtain a fragment of the adjacency list for the given vertex from one of the two or more read-only data structures, wherein the fragment of the adjacency list comprises a next pointer indicating another one of the two or more read-only data structures in which an immediately succeeding fragment of the adjacency list is stored: and
obtain the immediately succeeding fragment of the adjacency list from the other one of the two or more read-only data structures.

9. The system of claim 1 ,
wherein, at each given one of the respective levels in the mutable multilevel data structure at which one of the two or more read-only data structures is located other than the one of the two or more read-only data structures that comprises a consistent compressed sparse row representation of the graph structure at a given point in time, the vertex table comprises:
a respective entry referencing edge information in the edge table at the given level for each vertex in the graph structure for which a property or edge was modified between the time that the given level was created and the time that an immediately previous level in the mutable multilevel data structure was created; and
a respective entry referencing the vertex table at a previous level in the mutable multilevel data structure for each vertex in the graph structure for which no modification was made to a property or edge between the time that the given level was created and the time that an immediately previous level in the mut

Assignees

• Oracle Int Corp

Inventors

• Macko Peter
• Marathe Virendra J
• Seltzer Margo I

Classifications

• G06T11/26 Primary

  Drawing of charts or graphs · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F16/9024

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

• G06T11/206 Primary

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic