Patent ID: 9613164
Date: 2017-04-04
CPC Classifications: G06F

Claim:
1. A method of answering a query expressed as a graph, for a data network stored across a plurality of compute nodes as a graph-based index including a plurality of vertices connected by edges, the method comprising: marking a constant vertex in the query expressed as the graph and transmitting the query to one of the plurality of compute nodes storing a first vertex, from among the plurality of vertices of the graph-based index, that corresponds to the constant vertex, the query including the constant vertex and a plurality of variable vertices connected by an edge label; determining vertices connected to the first vertex and preparing a candidate substitution list for each of the plurality of variable vertices by looking at the neighborhood of the constant vertex and the edge label to the constant vertex; choosing a first candidate from the candidate substitution list corresponding to a first variable vertex, among the plurality of variable vertex, and substituting candidates for the other variable vertices in among the plurality of variable vertex from the respective candidate substitution list; when it is determined that any of the candidate substitution list associated with other variable vertices corresponding to the chosen first candidate is empty, choosing a second candidate from the candidate list corresponding to the first variable vertex, and repeating substituting candidates for the other variable vertices in among the plurality of variable vertex; and preparing an answer to the query based on a result of the substitution of candidates from the candidate substitution list of each of the plurality of variable vertices.