Back to results
US 11,693,848 B2Granted
Approaches for knowledge graph pruning based on sampling and information gain theory
AssigneeAccenture Global Solutions Limited
InventorsTeresa Sheausan Tung, Colin Anil Puri, Zhijie Wang
Life of this patent
Estimating the term…
Abstract
Knowledge graph systems are disclosed for implementing multiple approaches, including stand alone or combined approaches, for knowledge graph pruning. The approaches are based on graph sampling work such as, for example, information gain theory. The approaches are applied by a knowledge graph system to perform schema pruning, automatic graph pruning, and query correlation for improving query performance.
Claims20
A knowledge graph system comprising:
- a memory for storing computer instructions;
- a processor in communication with the memory, the processor being configured to execute the computer instructions to:
- receive a query request;
- analyze historical query patterns run on a knowledge graph for previously received query results that are similar to the query request to obtain an analysis of a usage history of the knowledge graph;
- select one or more candidate traversal paths included in the knowledge graph based on the analysis to prune the knowledge graph into a subgraph, wherein a candidate traversal path is comprises at least one candidate entity node and at least one candidate edge connected to the at least one candidate entity node;
- receive a candidate list including the one or more candidate traversal paths;
- determine a historical knowledge graph schema used on the knowledge graph based on the analysis, the historical knowledge graph schema being used to ingest the knowledge graph;
- compare the historical knowledge graph schema with the candidate list;
- remove candidate traversal paths from the knowledge graph;
- and
- remove at least one node type from the historical knowledge graph schema based on the comparison to generate a pruned knowledge graph schema for ingesting an updated knowledge graph.
8 more elements
A knowledge graph pruning method comprising:
- receiving a query request;
- analyzing historical query patterns run on a knowledge graph for previously received query results that are similar to the query request to obtain an analysis of a usage history of the knowledge graph;
- selecting one or more candidate traversal paths included in the knowledge graph based on the analysis to prune the knowledge graph into a subgraph, wherein a candidate traversal path comprises at least one candidate entity node and at least one candidate edge connected to the at least one candidate entity node;
- receiving a candidate list including the one or more candidate traversal paths;
- analyzing the historical query patterns;
- determining a historical knowledge graph schema used on the knowledge graph based on the analysis, the historical knowledge graph schema being used to ingest the knowledge graph;
- comparing the historical knowledge graph schema with the candidate list;
- removing candidate traversal paths from the knowledge graph;
- and
- removing at least one node type from the historical knowledge graph schema based on the comparison to generate a pruned knowledge graph schema for ingesting an updated knowledge graph.
7 more elements
A non-transitory machine-readable medium for storing instructions, the instructions configured to, when executed by a processor, cause the processor to:
- receive a query request;
- analyze historical query patterns run on a knowledge graph for previously received query results that are similar to the query request to obtain an analysis of a usage history of the knowledge graph;
- select one or more candidate traversal paths included in the knowledge graph based on the analysis to prune the knowledge graph into a reduced graph, wherein a candidate traversal path comprises at least one candidate entity node and at least one candidate edge connected to the at least one candidate entity node;
- receive a candidate list including the one or more candidate traversal paths;
- analyze the historical query patterns;
- determine a historical knowledge graph schema used on the knowledge graph based on the analysis, the historical knowledge graph schema being used to ingest the knowledge graph;
- compare the historical knowledge graph schema with the candidate list;
- remove candidate traversal paths from the knowledge graph;
- and
- remove at least one node type from the historical knowledge graph schema based on the comparison to generate a pruned knowledge graph schema for ingesting an updated knowledge graph.
7 more elements
Dependencies are inferred from the claim text.