Incremental graph computations for querying large graphs

A network device comprising:

• a memory comprising results of a query on a graph linking data, a change to the graph, and instructions;
• and
• one or more processors in communication with the memory, wherein the one or more processors execute the instructions to:
• determine that the change to the graph is localizable when the change to the graph can be determined by inspecting only graph nodes within a specified number of hops of any graph node indicated by the change to the graph;
• determine that the change to the graph is relatively bounded when a cost of an incremental change is expressed as a polynomial function in terms of the change to the graph, a query size, and a change in an affected area of the query caused by the change to the graph;
• and
• update the results of the query based on the change to the graph without determining updated results of the query over the graph when the change to the graph is localizable and relatively bounded, the updating performed by:
• discovering affected nodes that are affected by the change to the graph,
• updating data associated with the affected nodes resulting in updated data, and
• applying the updated data to the results of the query.

A non-transitory computer readable medium comprising a computer program product for use by a network device, the computer program product comprising computer executable instructions stored on the non-transitory computer readable medium such that when executed by a processor cause the network device to:

• receive results of a query on a graph linking data;
• receive a change to the graph;
• determine that the change to the graph is localizable-when the change to the graph can be determined by inspecting only graph nodes within a specified number of hops of any graph node indicated by the change to the graph;
• determine that the change to the graph is relatively bounded when a cost of an incremental change is expressed as a polynomial function in terms of the change to the graph, a query size, and a change in an affected area of the query caused by the change to the graph;
• and
• update, by the processor, the results of the query based on the change to the graph without determining updated results of the query over the graph when the change to the graph is localizable and relatively bounded, the updating performed by:
• discovering affected nodes that are affected by the change to the graph,
• updating data associated with the affected nodes resulting in updated data, and
• applying the updated data to the results of the query.