Semi structured question answering system

Patent metadata

Field	Value
Publication number	US-9842166-B1
Application number	US-201414455142-A
Country	US
Kind code	B1
Filing date	Aug 8, 2014
Priority date	Aug 8, 2014
Publication date	Dec 12, 2017
Grant date	Dec 12, 2017

Abstract

In one example embodiment, a computer system includes at least one processor and a memory storing a data graph and instructions. The instructions, when executed by the at least one processor, cause the system to generate a template sentence based on a fact including a first node, a second node and a string, wherein the first node and the second node exist in the data graph and the string represents a fact that is absent from the data graph, search the internet for a document including the template sentence, and upon determining the internet includes the document with the template sentence, infer the fact by generating a series of connections between nodes and edges of the data graph that together with the first node and the second node are configured to represent the fact, the series of connections defining a path, in the data graph, from the first node to the second node.

First claim

What is claimed is:

1. A computer system comprising:
at least one processor; and
memory storing:
a data graph, and
instructions that, when executed by the at least one processor, cause the system to:
receive a query based on a first node of the data graph and a fact,
determine whether the fact is absent from the data graph, and
upon determining the fact is absent from the data graph:
determine an answer to the query by following a path starting at the first node and ending at a second node, the path including at least one third node between the first node and the second node, wherein
 the data graph includes a first edge configured to connect the at least one third node with the first node,
 the data graph includes a second edge configured to connect the at least one third node with the second node,
 the path links the first node to the at least one third node via the first edge, and
 the path links the at least one third node to the second node via the second edge, and
return a property associated with the second node as the answer to the query, the property being linked to the second node via a third edge.

2. The computer system of claim 1 , wherein the path is based on an attribute of the first node.

3. The computer system of claim 1 , wherein the determining of the answer further includes:
determining an attribute of the first node associated with the query;
determining the attribute is absent from the data graph;
and
determining the absent fact based on the path.

4. The computer system of claim 1 , wherein
the query is formatted as a question based on the fact and the first node, and
the fact links the first node to the second node.

5. The computer system of claim 1 , wherein the instructions, when executed by the at least one processor, further cause the system to display the fact associated with the answer.

6. A computer system comprising:
at least one processor; and
memory storing:
a data graph, and
instructions that, when executed by the at least one processor, cause the system to:
determine whether a first fact is absent from the data graph, and
upon determining the first fact is absent from the data graph:
generate a template sentence based on a second fact including a first node, a second node and a string, wherein the first node and the second node exist in the data graph and the string represents the first fact that is absent from the data graph;
search the internet for a document including the template sentence; and
upon determining the internet includes the document with the template sentence:
infer the first fact by generating a series of connections between nodes and edges of the data graph that together with the first node and the second node are configured to represent the first fact, the series of connections defining a path, in the data graph, from the first node to the second node.

7. The computer system of claim 6 , wherein the search of the internet for the document includes:
crawling the internet to read a sentence in each of a plurality of documents;
parsing the sentence;
determining if an attribute associated with the first node and an attribute associated with the second node exist in the sentence;
upon determining the attribute associated with the first node and the attribute associated with the second node exist in the sentence, determine if the first node and the second node are linked based on the template sentence; and
upon determining the first node and the second node are linked based on the template sentence, the internet is determined to include the document with the template sentence.

8. The computer system of claim 6 , wherein the search of the internet for the document includes:
crawling a plurality of documents stored in the memory that are associated with documents on the internet to read a sentence in each of a plurality of documents;
parse the sentence;
determine if the parsed sentence matches the template sentence;
determine if an attribute associated with the first node and an attribute associated with the second node exist in the sentence; and
upon determining the parsed sentence matches the template sentence and the attribute associated with the first node and the attribute associated with the second node exist in the sentence, infer the second fact based on the parsed sentence.

9. The computer system of claim 6 , wherein the search of the internet for the document includes:
generating a parse tree associated with a sentence read from a document on the internet;
searching the parse tree for the first node and the second node; and
determining if the first node and the second node are linked based on the template sentence.

10. The computer system of claim 6 , wherein the first fact describes the first node, the second node and an edge absent from the data graph.

11. The computer system of claim 6 , further comprising:
traversing the data graph to find a plurality of paths from the first node to the second node; and
selecting one of the plurality of paths as the path.

12. The computer system of claim 11 , wherein selecting the path is based on at least one of a number times that the path repeats, a length of the path, a type of node traversed, and an abundance of the path relative to shorter paths.

13. The computer system of claim 6 , wherein the document includes a file that stores content.

14. The computer system of claim 6 , further comprising verifying the series of connections using a query based on the first fact and one of the first node and the second node.

15. The computer system of claim 6 , further comprising:
first receiving a query based on the first fact;
second receiving one of the first node and the second node as a variable associated with the query;
third receiving the other of the first node and the second node as an answer to the query;
traversing the data graph using the series of connections to determine if the answer to the query is the other of the first node and the second node;
repeating the second receiving, the third receiving and the traversing steps a number of times; and
verifying the series of connections between nodes and edges of the data graph as acceptable if the answer to the query is the other of the first node and the second node is at least a threshold number.

16. The computer system of claim 6 , further comprising:
receiving a query based on the first fact including one of the first node and the second node from an external system;
determining if the first fact exists in the data graph; and
upon determining the first fact does not exist in the data graph, returning an answer using the series of connections.

17. A method comprising:
determining whether an edge is absent from a data graph; and
upon determining the edge is absent from the data graph:
generating a template sentence based on a fact including a first node, a second node and a string, wherein the first node and the second node exist in the data graph and the string represents the edge that is absent from the data graph;
searching the internet for a document including the template sentence;
upon determining the template sentence is in the document, determine a relationship between the first node and the second node; and
inferring the edge based on the relationship by generating a series of connections between nodes and edges of the data graph that together with the first node and the second node are configured to represent the fact, the series of connections defining a path, in the data graph, from the first node to the second node.

Assignees

• Google Inc
• Google Llc

Inventors

• Leviathan Yaniv
• Segalis Eyal
• Tzur Yoav
• Chechik Gal

Classifications

• G06F16/9538

  Presentation of query results · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/951 Primary

  Indexing; Web crawling techniques · CPC title

• G06F17/30864 Primary

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic