Graph processing using a mutable multilevel graph representation

• US 9,734,607 B2
• Filed: 09/10/2014
• Issued: 08/15/2017
• Est. Priority Date: 09/10/2014
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Marathe, Virendra J., Macko, Peter, Seltzer, Margo I.
• Primary Examiner(s): Kim, Taelor
• Assistant Examiner(s): Brooks, David T
• Application Number:
  US14/483,052
• Publication Number:
  US 20160071233A1
• Time in Patent Office: 1,070 Days
• Field of Search: None
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

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.

Claims

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 mutable multilevel data structure was created.

10. 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 one or more of:

a deletion vector indicating, 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, whether or not each edge of the vertex was deleted 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;

an adjacency list length for each vertex in the graph structure that is represented by an element in the vertex table;

or

a directed or undirected vertex degree for each vertex in the graph structure that is represented by an element in the vertex table.

11. The system of claim 3,

wherein in response to receiving a request to modify the graph structure, the graph processing module is configured to update the mutable multilevel data structure;

and

wherein to update the mutable multilevel data structure, the graph processing module is configured to modify a vertex table in the single writeable data structure to reflect one or more of;

an addition of a vertex to the graph structure;

a deletion of a vertex from the graph structure;

an addition of an edge to or from a vertex in the graph structure;

or

a deletion of an edge to or from a vertex in the graph structure.

12. 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 copy-on-write enabled indirection table, each element of which represents a vertex in the graph structure for which a modification has been made since the time at which an immediately previous level in the mutable multilevel data structure was created; and

a plurality of data pages;

wherein each of the plurality of data pages comprises no more than a pre-determined maximum number of vertex table elements; and

wherein each vertex table element contains a NIL value or a vertex object comprising a dynamically sized array indicating edges to or from a particular vertex in the graph structure that have been added or deleted since the time at which an immediately previous level in the mutable multilevel data structure was created.

13. The system of claim 1, wherein the graph processing module is further configured to:

merge two of the two or more read-only data structures that are on adjacent levels of the mutable multilevel data structure to create a new read-only data structure;

replace the two of the two or more read-only data structures with the new read-only data structure on one of the adjacent levels of the mutable multilevel data structure; and

delete the other one of the adjacent levels of the mutable multilevel data structure.

14. The system of claim 1,

wherein the memory comprises a local system memory;

wherein the system further comprises a persistent memory component that stores the mutable multilevel data structure in its entirety;

wherein the mutable multilevel data structure is larger than an available portion of the local system memory; and

wherein to perform the computation on the graph structure, the system is configured to load one or more portions of the mutable multilevel data structure from the persistent memory component into the local system memory on an as-needed basis.

15. 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, the edge table comprises a respective adjacency list for each vertex in the graph structure for which the vertex table at the given level comprises a respective entry referencing edge information in the edge table at the given level.

16. The system of claim 1,

wherein to perform the computation on the graph structure, the graph processing module is configured to:

receive an information stream comprising a plurality of requests, each indicating one or more edges to be added to the graph structure or one or more edges to be deleted from the graph structure;

advance a sliding window into the mutable multilevel data structure indicating a portion of the mutable multilevel data structure in which edge information or deletion vectors represented in the two or more read-only data structures of the mutable multilevel data structure are to be considered during the performance of the computation, wherein the sliding window comprises edge information for the one or more edges included in the most recently received request to add one or more edges to the graph structure or a deletion vector indicating the one or more edges included in the most recently received request to delete one or more edges from the graph structure; and

reconstruct the adjacency list for the given vertex of the graph structure using only edge information or deletion vectors in the portion of the mutable multilevel data structure indicated by the sliding window; and

wherein to advance the sliding window, the graph processing module is configured to designate a lowest level of the mutable multilevel data structure at which edge information or deletion vectors represented in the two or more read-only data structures of the mutable multilevel data structure are to be considered during the performance of the computation.

17. A method, comprising:

receiving a request to perform a computation on a graph structure, wherein the graph structure is represented by a mutable multilevel data structure stored in a memory; and

in response to said receiving, a graph processing module reconstructing 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;

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; and

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.

18. The method of claim 17,

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;

and

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.

19. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to implement a graph processing module, wherein the graph processing module is configured to perform:

receiving a request to perform a computation on a graph structure, wherein the graph structure is represented by a mutable multilevel data structure stored in a memory; and

in response to receiving the request, reconstructing 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;

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.

20. The non-transitory, computer-readable storage medium of claim 19,

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;

wherein the graph processing module is further configured to perform creating a new read-only data structure at a new level of the mutable multilevel data structure;

wherein creating the new read-only data structure comprises, 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;

determining 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

performing the determined copy operation;

wherein the determining 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.