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

One or more non-transitory 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;
• and
• the directed graph contains a first vertex that has first dense identifier and a first sparse identifier;
• storing a first bidirectional map that, for each vertex of the directed graph, associates the sparse identifier of the vertex with the dense identifier of the vertex;
• cloning a second bidirectional map from the first bidirectional map;
• creating a first version of the directed graph that is based on the first bidirectional map;
• creating a second version of the directed graph that is based on the second bidirectional map;
• executing a plurality of change descriptors that describe changes to the second version of the directed graph, including a first change descriptor that removes the first vertex from the directed graph and a second change descriptor that adds a second vertex to the directed graph, wherein the second vertex has the first dense identifier and a second sparse identifier;
• updating the second bidirectional map to reflect said executing said plurality of change descriptors, including remapping the first dense identifier to the second sparse identifier;
• concurrently providing access to the first version and the second version of the directed graph to one or more clients.

One or more computers configured to:

• store 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;
• and
• the directed graph contains a first vertex that has first dense identifier and a first sparse identifier;
• store a first bidirectional map that, for each vertex of the directed graph, associates the sparse identifier of the vertex with the dense identifier of the vertex;
• clone a second bidirectional map from the first bidirectional map;
• create a first version of the directed graph that is based on the first bidirectional map;
• create a second version of the directed graph that is based on the second bidirectional map;
• execute a plurality of change descriptors that describe changes to the second version of the directed graph, including a first change descriptor that removes the first vertex from the directed graph and a second change descriptor that adds a second vertex to the directed graph, wherein the second vertex has the first dense identifier and a second sparse identifier;
• update the second bidirectional map to reflect said executing said plurality of change descriptors, including remapping the first dense identifier to the second sparse identifier;
• concurrently provide access to the first version and the second version of the directed graph to one or more clients.