System and method for data management in large data networks
A system and method for storing an input data network, in the form of graph is provided. The system includes a master node and a plurality of slave nodes. The master node is operable to receive the data network in the form of a graph, the graph including a plurality of vertices connected by edges; calculate a probability of co-retrieval for each of the plurality of vertices; and assign each of the plurality of vertices to one of the plurality of compute nodes based on the calculated probability of co-retrieval. Another method and system are provided for converting a dataset into a graph based index and storing the index on disk. Respective systems and methods of querying such data networks are also provided.
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.
2. The method of claim 1 , wherein the plurality of compute nodes are split across a compute cloud.
3. The method of claim 1 , wherein when the result with distance constraints are pruned, a variable vertex with the smallest, non-null candidate result is set and iterated over all candidates substituting the other variable vertices among the plurality of variable vertex one at a time for the respective variable vertex.
4. The method of claim 3 , further comprising:
determining whether the substituted candidate satisfies all distance constraints associated with the respective variable vertex;
discarding the substituted candidate if one of the distance constraints is violated; and
updating the candidate substitution list if the distance constraints are met.