Efficient method for subgraph pattern matching

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

• receiving a plurality of vertices of a graph, wherein each vertex has a distinct offset within a sequence of offsets;
• storing an edge array of edges, wherein each edge of said edge array:
• originates at a respective originating vertex of said graph, terminates at a terminating vertex of said graph, and comprises edge data;
• wherein said edge array is sorted by the offsets of the originating vertices of respective edges;
• storing an index array of index entries, wherein each index entry of said index array corresponds to a respective vertex of said graph, wherein the offset of said each index entry within said index array is the same as the offset of said respective vertex, wherein said each index entry associates an edge offset of an edge within said edge array with an offset of said respective vertex, wherein said edge originates at said respective vertex, wherein said edge offset is the least offset, within said edge array, of all edges that originate at said respective vertex;
• storing an array of edge data of each edge of said edge array, wherein the offset of said each edge data within said array of edge data is the same as the offset of said respective edge within said edge array, wherein said each edge data contains edge data of said respective edge;
• selecting a candidate subset of edges that originate at a current vertex, wherein the edge data of each candidate edge of said candidate subset includes a same query edge data, wherein said selecting a candidate subset is based on said index array and said array of edge data;
• selecting a result subset of vertices from the terminating vertices of edges of said candidate subset.

A system comprising:

• a memory;
• connected to said memory, one or more processors configured to:
• store, in said memory, a plurality of vertices of a graph, wherein each vertex of said graph has a distinct offset within a sequence of offsets;
• store, in said memory, an edge array of edges, wherein each edge of said edge array:
• originates at a respective originating vertex of said graph, terminates at a terminating vertex of said graph, and comprises edge data;
• wherein said edge array is sorted by the offsets of the originating vertices of respective edges;
• store, in said memory, an index array of index entries, wherein each index entry of said index array corresponds to a respective vertex of said graph, wherein the offset of said each index entry within said index array is the same as the offset of said respective vertex, wherein said each index entry associates an edge offset of an edge within said edge array with an offset of said respective vertex, wherein said edge originates at said respective vertex, wherein said edge offset is the least offset, within said edge array, of all edges that originate at said respective vertex;
• store, in said memory, an array of edge data of each edge of said edge array, wherein the offset of said each edge data within said array of edge data is the same as the offset of said respective edge within said edge array, wherein said each edge data contains edge data of said respective edge;
• select a candidate subset of edges that originate at a current vertex, wherein the edge data of each candidate edge of said candidate subset includes a same query edge data, wherein said selecting a candidate subset is based on said index array and said array of edge data;
• select a result subset of vertices from the terminating vertices of edges of said candidate subset.