Knowledge storage and retrieval system and method

• US 8,719,318 B2
• Filed: 05/17/2013
• Issued: 05/06/2014
• Est. Priority Date: 11/28/2000
• Status: Expired due to Term

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Evi Technologies Ltd. (Amazon.com, Inc.)
• Inventors: Tunstall-Pedoe, William
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/896,857
• Publication Number:
  US 20130254221A1
• Time in Patent Office: 354 Days
• Field of Search: 707/607, 707/608, 707/687, 707/705, 707/790, 707/813, 707/821
• US Class Current: 707/813
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 40/237 Lexical tools
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for representing, storing and retrieving real-world knowledge on a computer or network of computers is disclosed. Knowledge is broken down into permanent atomic “facts” which can be stored in a standard relational database and processed very efficiently. It also provides for the efficient querying of a knowledge base, efficient inference of new knowledge and translation into and out of natural language. Queries can also be processed with full natural language explanations of where the answers came from. The method can also be used in a distributed fashion enabling the system to be a large network of computers and the technology can be integrated into a web browser adding to the browser'"'"'s functionality.

Claims

1. A computer-implemented method, comprising:

receiving a natural language question comprising a sequence of words;

identifying a first translation template of a plurality of translation templates using at least a first word of the sequence of words, the first translation template including a sequence of known and unknown strings, a first query and a second query, a first known string of the known and unknown strings corresponding to the first word;

identifying a first object in a knowledge base using a second word of the sequence of words and the first query of the first translation template; and

generating one or more results using the knowledge base, the first object, and the second query of the first translation template.

2. The method of claim 1, wherein generating the one or more results comprises rejecting a first result of the one or more results where the first result is incompatible with an object class corresponding to the first object.

3. The method of claim 1, wherein the one or more results comprise a plurality of results, the method further comprising generating a request for further information including natural language representations of the plurality of results.

4. The method of claim 1, wherein the first translation template includes a third query, the method further comprising:

identifying a first relation in the knowledge base using a third word of the sequence of words and the third query of the first translation template; and

wherein generating the one or more results comprises using the first relation.

5. The method of claim 1, wherein identifying the first object comprises:

substituting the second word of the sequence of words into the first query;

executing the first query with reference to the knowledge base thereby generating one or more intermediate results corresponding to the first object; and

substituting the one or more intermediate results corresponding to the first object into the second query.

6. The method of claim 1, further comprising generating an explanation representing how the one or more results were generated, the explanation including a natural language translation of the second query and one or more processing steps of the second query with reference to the knowledge base.

7. The method of claim 1, wherein generating the one or more results comprises inferring new knowledge not statically stored in the knowledge base from knowledge that is statically stored in the knowledge base.

8. A computing system for responding to natural language input, comprising:

one or more data stores having a knowledge base stored therein; and

one or more computing devices configured to;

receive a natural language question comprising a sequence of words;

identify a first translation template of a plurality of translation templates using at least a first word of the sequence of words, the first translation template including a sequence of known and unknown strings, a first query and a second query, a first known string of the known and unknown strings corresponding to the first word;

identify a first object in the knowledge base using a second word of the sequence of words and the first query of the first translation template; and

generate one or more results using the knowledge base, the first object, and the second query of the first translation template.

9. The computing system of claim 8, wherein the one or more computing devices are configured to generate the one or more results by rejecting a first result of the one or more results where the first result is incompatible with an object class corresponding to the first object.

10. The computing system of claim 8, wherein the one or more results comprise a plurality of results, and wherein the one or more computing devices are further configured to generate a request for further information including natural language representations of the plurality of results.

11. The computing system of claim 8, wherein the first translation template includes a third query, and wherein the one or more computing devices are configured to:

identify a first relation in the knowledge base using a third word of the sequence of words and the third query of the first translation template; and

generate the one or more results using the first relation.

12. The computing system of claim 8, wherein the one or more computing devices are configured to identify the first object by:

substituting the second word of the sequence of words into the first query;

executing the first query with reference to the knowledge base thereby generating one or more intermediate results corresponding to the first object; and

substituting the one or more intermediate results corresponding to the first object into the second query.

13. The computing system of claim 8, wherein the one or more computing devices are further configured to generate an explanation representing how the one or more results were generated, the explanation including a natural language translation of the second query and one or more processing steps of the second query with reference to the knowledge base.

14. The computing system of claim 8, wherein the one or more computing devices are configured to generate the one or more results by inferring new knowledge not statically stored in the knowledge base from knowledge that is statically stored in the knowledge base.

15. A computer program product for responding to natural language input, comprising one or more non-transitory computer-readable media having computer program instructions stored therein, the computer program instructions being configured such that, when executed, the computer program instructions cause one or more computing devices to:

receive a natural language question comprising a sequence of words;

identify a first translation template of a plurality of translation templates using at least a first word of the sequence of words, the first translation template including a sequence of known and unknown strings, a first query and a second query, a first known string of the known and unknown strings corresponding to the first word;

identify a first object in a knowledge base using a second word of the sequence of words and the first query of the first translation template; and

generate one or more results using the knowledge base, the first object, and the second query of the first translation template.

16. The computer program product of claim 15, wherein the computer program instructions are configured such that, when executed, the computer program instructions cause the one or more computing devices to generate the one or more results by rejecting a first result of the one or more results where the first result is incompatible with an object class corresponding to the first object.

17. The computer program product of claim 15, wherein the one or more results comprise a plurality of results, and wherein the computer program instructions are further configured such that, when executed, the computer program instructions cause the one or more computing devices to generate a request for further information including natural language representations of the plurality of results.

18. The computer program product of claim 15, wherein the first translation template includes a third query, and wherein the computer program instructions are further configured such that, when executed, the computer program instructions cause the one or more computing devices to:

identify a first relation in the knowledge base using a third word of the sequence of words and the third query of the first translation template; and

generate the one or more results using the first relation.

19. The computer program product of claim 15, wherein the computer program instructions are configured such that, when executed, the computer program instructions cause the one or more computing devices to identify the first object by:

substituting the second word of the sequence of words into the first query;

executing the first query with reference to the knowledge base thereby generating one or more intermediate results corresponding to the first object; and

substituting the one or more intermediate results corresponding to the first object into the second query.

20. The computer program product of claim 15, wherein the computer program instructions are further configured such that, when executed, the computer program instructions cause the one or more computing devices to generate an explanation representing how the one or more results were generated, the explanation including a natural language translation of the second query and one or more processing steps of the second query with reference to the knowledge base.

21. The computer program product of claim 15, wherein the computer program instructions are configured such that, when executed, the computer program instructions cause the one or more computing devices to generate the one or more results by inferring new knowledge not statically stored in the knowledge base from knowledge that is statically stored in the knowledge base.