Patent Document ID: 20170124218
Application ID: 14932076
Patent Status: 0

Claim One:
1. A method for searching a graph to identify cliques using a set of processing elements (PEs), wherein a first PE of the set of PEs has access to a set of vertices adjacent to a seed vertex of the graph, the method comprising: a) generating, by the first PE, a data structure for each intermediate vertex of the set of vertices, the data structure indicating the respective intermediate vertex and an additional list of zero or more intermediate vertices of the set of vertices; b) storing, by the first PE, the generated data structures on a data buffer; c) for each buffered data structure of the buffered data structures: receiving, by an available PE of the set of PEs, the buffered data structure from the data buffer; configuring the available PE to receive an adjacency list of the intermediate vertex indicated in the respective data structure and to select from the adjacency list of the intermediate vertex a set of further vertices that are adjacent to the seed vertex and are part of the additional list; when at least one further vertex is selected, repeating steps a) through c) with the available PE being the first PE and the set of further vertices being the set of vertices; and when no further vertex is selected, generating a clique candidate using the seed vertex and the intermediate vertices that have been processed in step c); and d) selecting, among the clique candidates having overlapping pairs of vertices, cliques comprising a maximum number of vertices and selecting other cliques as clique candidates having non-overlapping pairs of vertices with other clique candidates.