Multi-source breadth-first search (MS-BFS) technique and graph processing system that applies it

One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

• during each iteration of a first sequence of iterations of a multi-source breadth first search (MS-BFS), updating a first matrix that contains a plurality of elements that use a first primitive integer type having a first width to record a distance from a source vertex of a graph to a vertex of the graph;
• detecting that a count of iterations of the first sequence of iterations exceeds a threshold;
• creating, in response to the detecting, a second matrix that contains a plurality of elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to a vertex of the graph;
• during each iteration of a second sequence of iterations of the MS-BFS, updating the second matrix.

A device comprising:

• a memory configured to store a graph;
• at least one processor connected to the memory and configured to:
• during each iteration of a first sequence of iterations of a multi-source breadth first search (MS-BFS), updating a first matrix that contains a plurality of elements that use a first primitive integer type having a first width to record a distance from a source vertex of the graph to a vertex of the graph;
• detecting that a count of iterations of the first sequence of iterations exceeds a threshold;
• creating, in response to the detecting, a second matrix that contains a plurality of elements that use a second primitive integer type having a second width that is larger than the first width to record a distance from a source vertex of the graph to a vertex of the graph;
• during each iteration of a second sequence of iterations of the MS-BFS, updating the second matrix.