Knowledge storage and retrieval system and method

• US 8,468,122 B2
• Filed: 11/12/2008
• Issued: 06/18/2013
• 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:
  US12/269,707
• Publication Number:
  US 20090070284A1
• Time in Patent Office: 1,679 Days
• Field of Search: 707/600, 707/607, 707/609, 707/687, 707/790, 707/813, 707/899, 707/821
• US Class Current: 707/607
• 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 for responding to a query initiated at a user device and directed to a knowledge base, the knowledge base having data stored therein representing first knowledge about a plurality of objects using a plurality of relationships among the objects, wherein selected ones of the objects are associated with class objects identifying corresponding classes for the selected objects using class member objects that define class member relationships between the selected objects and the corresponding classes, the method comprising facilitating presentation of a response to the query at the user device using one or more computing devices, the response having been generated using second knowledge not statically stored or represented in the at least one knowledge base prior to receipt of the query, the second knowledge having been generated by inference from the first knowledge in response to the query, the inference including retrieving one or more first facts included in the first knowledge, the first facts corresponding to first ones of the objects and first ones of the relationships, and generating one or more second facts from the first facts that express at least one new relationship for at least one of the one or more first objects.

2. The method of claim 1 wherein the second knowledge was inferred with reference to the relationships.

3. The method of claim 1 further comprising facilitating initiation of the query at the user device.

4. The method of claim 3 wherein facilitating initiation of the query comprises facilitating entry of a natural language question.

5. The method of claim 4 wherein facilitating entry of the natural language question comprises facilitating entry of a text string into a URL window in a browser environment.

6. The method of claim 3 further comprising facilitating presentation of a plurality of query candidates at the user device.

7. The method of claim 6 wherein at least one of the query candidates was generated by translation of a natural language question entered at the user device, and wherein translation of the natural language question included generation of at least one sub-string from a string of text corresponding to the natural language question, and selection of at least one of a plurality of query template components corresponding to the at least one sub-string.

8. The method of claim 7 wherein translation of the natural language question further included substitution of the selected query template components into variables associated with a query generator.

9. The method of claim 7 wherein translation of the natural language question further included generation of a query template including the plurality of query template components by designation of a plurality of predefined text sub-strings and a plurality of variables to which the predefined text sub-strings correspond, and by definition of 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 substituted for the corresponding variables.

10. The method of claim 1 wherein facilitating presentation of the response at the user device comprises facilitating presentation of a natural language response which was generated with reference to second selected ones of the plurality of objects.

11. The method of claim 10 wherein the natural language response was generated with reference to translation objects associated with the second selected objects in the knowledge base.

12. The method of claim 11 wherein the translation objects comprise common translation objects and unique translation objects, each common translation object relating an associated one of the second selected objects with a common translation for the associated second selected object, each unique translation object relating an associated one of the second selected objects with a unique translation for the associated second selected object.

13. The method 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 second knowledge was inferred with reference to the relationships.

14. The method of claim 1 wherein the data representing the first knowledge further include temporal data representing temporal validity for at least some of the relationships.

15. A computer-implemented method for responding to a query initiated at a user device and directed to a knowledge base, the knowledge base having data stored therein representing first knowledge about a plurality of objects using a plurality of relationships among the objects, the knowledge base further having natural language translation objects associated therewith operable to translate between natural language and syntax associated with the knowledge base, the method comprising facilitating presentation of a response to the query at the user device using one or more computing devices, the response having been generated using second knowledge not statically stored or represented in the at least one knowledge base prior to receipt of the query, the second knowledge having been generated by inference from the first knowledge in response to the query, the response also having been generated using at least one of the natural language translation objects, wherein the inference includes retrieving one or more first facts included in the first knowledge, the first facts corresponding to first ones of the objects and first ones of the relationships, and generating one or more second facts from the first facts that express at least one new relationship for at least one of the one or more first objects.

16. The method of claim 15 wherein the second knowledge was inferred with reference to the relationships.

17. The method of claim 15 further comprising facilitating initiation of the query at the user device by facilitating entry of a natural language question.

18. The method of claim 17 wherein facilitating entry of the natural language question comprises facilitating entry of a text string into a URL window in a browser environment.

19. The method of claim 17 wherein the at least one natural translation object translated the natural language question by generation of at least one sub-string from a string of text corresponding to the natural language question, and selection of at least one of a plurality of query template components corresponding to the at least one sub-string.

20. The method of claim 19 wherein the at least one natural translation object further translated the natural language question by substitution of the selected query template components into variables associated with a query generator.

21. The method of claim 19 wherein the at least one natural translation object further translated the natural language question by generation of a query template including the plurality of query template components by designation of a plurality of predefined text sub-strings and a plurality of variables to which the predefined text sub-strings correspond, and by definition of 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 substituted for the corresponding variables.

22. The method of claim 15 further comprising facilitating presentation of a plurality of query candidates at the user device.

23. The method of claim 15 wherein facilitating presentation of the response at the user device comprises facilitating presentation of a natural language response which was generated with reference to selected ones of the plurality of objects and using the at least one natural language translation object.

24. The method of claim 23 wherein the natural language translation objects comprise common translation objects and unique translation objects, each common translation object relating an associated one of the objects with a common translation for the associated object, and each unique translation object relating an associated one of the objects with a unique translation for the associated object.

25. The method of claim 15 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 second knowledge was inferred with reference to the relationships.

26. The method of claim 15 wherein the data representing the first knowledge further include temporal data representing temporal validity for at least some of the relationships.

27. A system for responding to a query initiated at a user device, comprising:

one or more data stores having a knowledge base stored therein that includes data representing first knowledge about a plurality of objects using a plurality of relationships among the objects, wherein selected ones of the objects are associated with class objects identifying corresponding classes for the selected objects using class member objects that define class member relationships between the selected objects and the corresponding classes; and

one or more computing devices configured to generate a response to the query using second knowledge not statically stored or represented in the at least one knowledge base prior to receipt of the query, the second knowledge being generated by inference from the first knowledge in response to the query, the inference including retrieving one or more first facts included in the first knowledge, the first facts corresponding to first ones of the objects and first ones of the relationships, and generating one or more second facts from the first facts that express at least one new relationship for at least one of the one or more first objects.

28. The system of claim 27 wherein the one or more computing devices are configured to infer the second knowledge with reference to the relationships.

29. The system of claim 27 wherein the one or more computing devices are further configured generate a plurality of query candidates for presentation at the user device in response to the query.

30. The system of claim 29 wherein the one or more computing devices are configured to generate at least one of the query candidates by translation of a natural language question entered at the user device, and wherein translation of the natural language question includes generation of at least one sub-string from a string of text corresponding to the natural language question, and selection of at least one of a plurality of query template components corresponding to the at least one sub-string.

31. The system of claim 30 wherein the one or more computing devices are further configured to translate the natural language question by substitution of the selected query template components into variables associated with a query generator.

32. The system of claim 30 wherein the one or more computing devices are further configured to translate the natural language question by generation of a query template including the plurality of query template components by designation of a plurality of predefined text sub-strings and a plurality of variables to which the predefined text sub-strings correspond, and by definition of 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 substituted for the corresponding variables.

33. The system of claim 27 wherein the one or more computing devices are further configured to generate a natural language response to the query with reference to second selected ones of the plurality of objects.

34. The system of claim 33 wherein the one or more computing devices are configured to generate the natural language response with reference to translation objects associated with the second selected objects in the knowledge base.

35. The system of claim 34 wherein the translation objects comprise common translation objects and unique translation objects, each common translation object relating an associated one of the second selected objects with a common translation for the associated second selected object, each unique translation object relating an associated one of the second selected objects with a unique translation for the associated second selected object.

36. The system of claim 27 wherein the data representing the first knowledge in the one or more data stores 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 one or more computing devices are further configured to infer the second knowledge with reference to the relationships.

37. The system of claim 27 wherein the data representing the first knowledge in the one or more data stores further include temporal data representing temporal validity for at least some of the relationships.

38. A system for responding to a query initiated at a user device, comprising:

one or more data stores having a knowledge base stored therein that includes data representing first knowledge about a plurality of objects using a plurality of relationships among the objects, the knowledge base further having natural language translation objects associated therewith operable to translate between natural language and syntax associated with the knowledge base; and

one or more computing devices configured to generate a response to the query using at least one of the natural language translation objects and second knowledge not statically stored or represented in the at least one knowledge base prior to receipt of the query, the second knowledge being generated by inference from the first knowledge in response to the query, the inference including retrieving one or more first facts included in the first knowledge, the first facts corresponding to first ones of the objects and first ones of the relationships, and generating one or more second facts from the first facts that express at least one new relationship for at least one of the one or more first objects.

39. The system of claim 38 wherein the one or more computing devices are configured to infer the second knowledge with reference to the relationships.

40. The system of claim 38 wherein the one or more computing devices are configured to use the at least one natural translation object to translate a natural language question corresponding to the query by generation of at least one sub-string from a string of text corresponding to the natural language question, and selection of at least one of a plurality of query template components corresponding to the at least one sub-string.

41. The system of claim 40 wherein the one or more computing devices are further configured to use the at least one natural translation object to translate the natural language question by substitution of the selected query template components into variables associated with a query generator.

42. The system of claim 40 wherein the one or more computing devices are further configured to use the at least one natural translation object to translate the natural language question by generation of a query template including the plurality of query template components by designation of a plurality of predefined text sub-strings and a plurality of variables to which the predefined text sub-strings correspond, and by definition of 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 substituted for the corresponding variables.

43. The system of claim 38 wherein the one or more computing devices are further configured to generate a plurality of query candidates for presentation at the user device in response to the query.

44. The system of claim 38 wherein the one or more computing devices are further configured to generate a natural language response with reference to selected ones of the plurality of objects and using the at least one natural language translation object.

45. The system of claim 44 wherein the natural language translation objects comprise common translation objects and unique translation objects, each common translation object relating an associated one of the objects with a common translation for the associated object, and each unique translation object relating an associated one of the objects with a unique translation for the associated object.

46. The system of claim 38 wherein the data representing the first knowledge in the one or more data stores 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 one or more computing devices are further configured to infer the second knowledge with reference to the relationships.

47. The system of claim 38 wherein the data representing the first knowledge in the one or more data stores further include temporal data representing temporal validity for at least some of the relationships.