Knowledge storage and retrieval system and method

• US 7,013,308 B1
• Filed: 11/21/2001
• Issued: 03/14/2006
• 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): Metjahic, Safet
• Assistant Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/990,188
• Time in Patent Office: 1,574 Days
• Field of Search: 707100-1041, 707/3, 707/5, 707/4, 707/1, 706/52
• US Class Current: 707/709
• 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. At least one computer-readable medium having computer program instructions embodied therein for interacting with at least one knowledge base, the at least one knowledge base having data stored therein representing first knowledge about a plurality of objects using a plurality of relationships between pairs of the objects, the computer program instructions comprising:

first computer program instructions operable to interact with the at least one knowledge base and, in response to a query having a predetermined format, generate second knowledge not represented in the at least one knowledge base from the first knowledge, the data representing the first knowledge including temporal data representing temporal validity for at least some of the relationships; and

second computer program instructions operable to respond to the query using at least one of the first knowledge and the second knowledge.

2. The at least one computer-readable medium of claim 1 wherein the first computer program instructions are operable to infer the second knowledge with reference to the relationships.

3. The at least one computer-readable medium of claim 1 wherein at least a portion of the first and second computer program instructions are part of a plug-in application for use with a client browser application.

4. The at least one computer-readable medium of claim 1 wherein at least a portion of the first and second computer program instructions are part of a server-side application.

5. The at least one computer-readable medium of claim 1 wherein the computer program instructions further comprise third computer program instructions operable to generate the query.

6. The at least one computer-readable medium of claim 5 wherein the third computer program instructions are operable to generate the query in response to query data representing a natural language question.

7. The at least one computer-readable medium of claim 6 wherein the natural language question is entered as a text string into a URL window in a browser environment, the third computer program instructions further being operable to determine whether the text string is a URL or the query data.

8. The at least one computer-readable medium of claim 5 wherein the third computer program instructions are operable to translate a natural language question into the query by generating at least one sub-string from a string of text corresponding to the natural language question, and selecting at least one of a plurality of query template components corresponding to the at least one sub-string to generate the query.

9. The at least one computer-readable medium of claim 8 wherein the third computer program instructions are further operable to substitute the selected query template components into variables associated with a query generator execution of which generates the query.

10. The at least one computer-readable medium of claim 8 further comprising fourth computer program instructions operable to generate a query template including the plurality of query template components by designating a plurality of predefined text sub-strings and a plurality of variables to which the predefined text sub-strings correspond, and by defining a query generator with respect to the variables, the query generator being operable to generate the query from selected ones of the predefined text sub-strings being substituted for the corresponding variables.

11. The at least one computer-readable medium of claim 5 wherein the third computer program instructions are further operable to generate a plurality of query candidates including the query.

12. The at least one computer-readable medium of claim 11 wherein the third computer program instructions are further operable to reject selected ones of the plurality of query candidates with reference to the knowledge base.

13. The at least one computer-readable medium of claim 11 wherein the third computer program instructions are further operable to present the plurality of query candidates for selection of the query.

14. The at least one computer-readable medium of claim 1 wherein the computer program instructions further comprise third computer program instructions operable to generate a natural language response to the query with reference to selected ones of the plurality of objects.

15. The at least one computer-readable medium of claim 14 wherein the third computer program instructions are operable to generate the natural language response with reference to translation objects associated with the selected objects in the knowledge base.

16. The at least one computer-readable medium of claim 15 wherein the translation objects comprise common translation objects and unique translation objects, the common translation objects relating an associated one of the selected objects with a common translation for the associated selected object, and the unique translation objects relating an associated one of the selected objects with a unique translation for the associated object.

17. The at least one computer-readable medium of claim 1 wherein the first computer program instructions are operable to implement a plurality of inference generators each of which is operable to generate facts not represented in the knowledge base with reference to at least one of the plurality of objects and at least one potential fact associated with the inference generator.

18. The at least one computer-readable medium of claim 17 wherein some of the plurality of inference generators are operable to generate facts with reference to the associated objects, the relationships corresponding to the associated objects, and the associated potential facts, and without reference to any processes external to the inference generator.

19. The at least one computer-readable medium of claim 17 wherein some of the plurality of inference generators are operable to generate facts with reference to the associated objects, the relationships corresponding to the associated objects, and the associated potential facts, and only after performing at least one additional operation using a at least one process external to the inference generator.

20. The at least one computer-readable medium of claim 1 wherein the data representing the first knowledge comprises a plurality of fact representations each corresponding to a relationship between a pair of the plurality of objects, each fact representation including a first object name corresponding to a first one of the plurality of objects, a second object name corresponding to a second one of the plurality of objects, and a relation object name identifying a relation object which defines the relationship between the first and second objects, and wherein the first computer program instructions are operable to infer the second knowledge with reference to the relationships.

21. A computer-implemented method for interacting with at least one knowledge base, the at least one knowledge base having data stored therein representing first knowledge about a plurality of objects using a plurality of relationships between pairs of the objects, the method comprising:

interacting with the at least one knowledge base and, in response to a query having a predetermined format, generating second knowledge not represented in the at least one knowledge base from the first knowledge, the data representing the first knowledge including temporal data representing temporal validity for at least some of the relationships; and

responding to the query having a predetermined format using at least one of the first knowledge and the second knowledge.

22. The method of claim 21 wherein the second knowledge is inferred with reference to the relationships.

23. The method of claim 21 further comprising generating the query.

24. The method of claim 23 wherein the query is generated in response to query data representing a natural language question.

25. The method of claim 24 wherein the natural language question is entered as a text string into a URL window in a browser environment, the method further comprising determining whether the text string is a URL or the query data.

26. The method of claim 23 further comprising translating a natural language question into the query by generating at least one sub-string from a string of text corresponding to the natural language question, and selecting at least one of a plurality of query template components corresponding to the at least one sub-string to generate the query.

27. The method of claim 26 further comprising substituting the selected query template components into variables associated with a query generator execution of which generates the query.

28. The method of claim 26 further comprising generating a query template including the plurality of query template components by designating a plurality of predefined text sub-strings and a plurality of variables to which the predefined text sub-strings correspond, and by defining a query generator with respect to the variables, the query generator being operable to generate the query from selected ones of the predefined text sub-strings being substituted for the corresponding variables.

29. The method of claim 23 further comprising generating a plurality of query candidates including the query.

30. The method of claim 29 further comprising rejecting selected ones of the plurality of query candidates with reference to the knowledge base.

31. The method of claim 29 further comprising presenting the plurality of query candidates for selection of the query.

32. The method of claim 21 further comprising generating a natural language response to the query with reference to selected ones of the plurality of objects.

33. The method of claim 32 further comprising generating the natural language response with reference to translation objects associated with the selected objects in the knowledge base.

34. The method of claim 33 wherein the translation objects comprise common translation objects and unique translation objects, the common translation objects relating an associated one of the selected objects with a common translation for the associated selected object, and the unique translation objects relating an associated one of the selected objects with a unique translation for the associated object.

35. The method of claim 21 further comprising implementing a plurality of inference generators each of which is operable to generate facts not represented in the knowledge base with reference to at least one of the plurality of objects and at least one potential fact associated with the inference generator.

36. The method of claim 35 wherein some of the plurality of inference generators are operable to generate facts with reference to the associated objects, the relationships corresponding to the associated objects, and the associated potential facts, and without reference to any processes external to the inference generator.

37. The method of claim 35 wherein some of the plurality of inference generators are operable to generate facts with reference to the associated objects, the relationships corresponding to the associated objects, and the associated potential facts, and only after performing at least one additional operation using a at least one process external to the inference generator.

38. The method of claim 21 wherein the data representing the first knowledge comprises a plurality of fact representations each corresponding to a relationship between a pair of the plurality of objects, each fact representation including a first object name corresponding to a first one of the plurality of objects, a second object name corresponding to a second one of the plurality of objects, and a relation object name identifying a relation object which defines the relationship between the first and second objects, and wherein the method further comprises inferring the second knowledge with reference to the relationships.

39. A system for storing and retrieving information from a knowledge base, comprising:

at least one memory having data corresponding to the knowledge base stored therein representing first knowledge about a plurality of objects using a plurality of relationships between pairs of the objects and temporal data representing temporal validity for at least some of the relationships; and

at least one central processing unit operable in association with the at least one memory to interact with the at least one knowledge base and, in response to a query having a predetermined format, generate second knowledge not represented in the at least one knowledge base from the first knowledge, and respond to the query using at least one of the first knowledge and the second knowledge.

40. The system of claim 39 wherein the at least one memory and the at least one central processing unit are connected via a memory bus.

41. The system of claim 39 wherein the at least one memory and the at least one central processing unit are connected via a local area network.

42. The system of claim 39 wherein the at least one memory and the at least one central processing unit are connected via a wide area network.