Method and apparatus for searching using an active ontology

• US 10,002,189 B2
• Filed: 12/22/2008
• Issued: 06/19/2018
• Est. Priority Date: 12/20/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Cheyer, Adam
• Primary Examiner(s): Park, Grace A
• Application Number:
  US12/341,743
• Publication Number:
  US 20090164441A1
• Time in Patent Office: 3,466 Days
• Field of Search: 707705, 707706-708, 707758, 707759
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/367 Ontology

Abstract

Embodiments of the present invention provide a method and apparatus for searching using an active ontology. One embodiment of a method for searching a database includes receiving a search string, where the search string comprises one or more words, generating a semantic representation of the search string in accordance with an ontology, searching the database using the semantic representation, and outputting a result of the searching.

Claims

1. A method for constructing database queries for searching at least one database, comprising:

receiving a user entered search string, the search string comprising one or more words;

identifying a first node in an ontology based on the one or more words of the search string, the first node being related to at least one of the one or more words in the search string, wherein the ontology includes at least one node representing a concept and at least one node representing an attribute of the concept;

constructing a first database query based on the identified first node in the ontology, the first database query comprising one or more attributes associated with the first node, and a respective value, from the search string, for each of the one or more attributes;

after constructing the first database query, searching at least one database using the first database query;

identifying, based on a frequency of occurrence of a pair of user events, a second node in the ontology, the second node associated with the first node, the second node representing a concept not represented by the received search string, wherein a first user event of the pair of user events corresponds to the first node and a second user event of the pair of user events corresponds to the second node, and wherein for each occurrence of the pair of user events, the first user event and the second user event occur within a predetermined time period;

constructing a second database query based on the identified second node;

after constructing the second database query, searching at least one database using the second database query; and

outputting results of the searching.

2. The method of claim 1, wherein identifying the first node in an ontology comprises:

splitting the search string into one or more tokens, where each of the one or more tokens represents at least one of the one or more words;

parsing the one or more tokens, using the ontology; and

producing an interpretation of the search string as a result of the parsing.

3. The method of claim 2, wherein parsing the one or more tokens comprises:

matching the one or more tokens to at least one node in the ontology.

4. The method of claim 2, wherein producing an interpretation of the search string comprises:

producing a plurality of interpretations of the search string;

assigning a weight to each of the plurality of interpretations, the weight indicating a confidence that an associated one of the plurality of interpretations is correct; and

selecting a one of the plurality of interpretations with a highest weight.

5. The method of claim 1, further comprising:

identifying one or more missing search criteria in the search string; and

selecting a default value for the one or more missing search criteria from at least one of;

a user profile and a user search history.

6. The method of claim 5, wherein the first database query further comprises an additional attribute having an additional value, wherein the additional value is the selected default value.

7. The method of claim 1, wherein the ontology further comprises:

a plurality of links connecting nodes of the ontology with one another, each of the plurality of links representing a relation between nodes linked thereby.

8. The method of claim 7, wherein at least one relation among nodes comprises an indication that one concept causes another concept.

9. The method of claim 7, wherein at least one relation among nodes comprises an indication that concepts represented by the nodes tend to occur together.

10. The method of claim 7, wherein at least one relation among nodes comprises an indication that one of the nodes represents at least one additional search criterion associated with a concept represented by another of the nodes.

11. The method of claim 1, wherein the ontology is customized for a particular purpose.

12. The method of claim 1, further comprising:

augmenting at least one of the first and second database queries by incorporating at least one additional attribute associated with at least one additional node linked to the identified first node.

13. The method of claim 1, wherein the second database query comprises:

at least one attribute associated with the first node; and

a value, from the search string, of the at least one attribute.

14. The method of claim 1, wherein the identified first node corresponds to a best weighted interpretation of user intent.

15. The method of claim 1, further comprising establishing at least one link between nodes based on observed behavior of at least one user.

16. The method of claim 15, wherein establishing the at least one link between nodes comprises establishing a link between two nodes responsive to a degree of observed co-occurrence of identification of the two nodes in response to receiving user queries.

17. The method of claim 1, wherein the ontology comprises an active ontology.

18. The method of claim 1, further comprising:

generating a log of nodes identified as being related to a plurality of search strings received over a period of time;

determining co-occurrences among the logged nodes; and

augmenting the ontology to include links among nodes based on frequency of the determined co-occurrences.

19. The method of claim 18, wherein generating a log comprises:

for each of a plurality of received search strings, storing a record comprising at least one of;

the search string, the identified node, the result, and a time stamp indicating a reception time of the search string.

20. The method of claim 1, wherein the second node is associated with the first node based on a link between the first node and the second node.

21. The method of claim 1, wherein the second node represents a concept not represented by the received search string, and wherein the second node is a concept node that does not match any of the words in the search string.

22. The method of claim 1, wherein the first node and the second node are identified at substantially the same time.

23. The method of claim 1, wherein the first node and the second node are identified prior to searching any database with either the first database query or the second database query.

24. The method of claim 1, further comprising:

selecting at least a first database from a plurality of databases in accordance with a constraint defined in the first database query, wherein searching at least one database using the first database query comprises searching the selected at least a first database using the first database query.

25. The method of claim 1, wherein:

searching at least one database using the first database query comprises searching a first database using the first database query to retrieve first results that satisfy one or more criteria defined in the first database query;

searching at least one database using the second database query comprises searching a second database using the second database query to retrieve second results that satisfy one or more criteria defined in the second database query, the second database is different from the first database; and

outputting results comprises outputting results based on the first result and the second results.

26. The method of claim 1, wherein:

the first node in the ontology represents a first user intent of performing a first action;

the second node in the ontology represents a second user intent of performing a second action; and

the first node and the second node are directly connected by a link in the ontology, the link representing a causal relationship between the first action and the second action.

27. The method of claim 1, wherein a keyword search with words from the user entered search string is not performed on the at least one database after receiving the user entered search string and prior to searching the at least one database using the first database query.

28. The method of claim 1, wherein the first database query represents a user intent for the user entered search string.

29. A non-transitory computer readable storage medium containing an executable program for constructing database queries for searching a database, wherein the program is configured to cause at least one processor to perform the steps of:

receiving a user entered search string, the search string comprising one or more words;

identifying a first node in an ontology based on the one or more words of the search string, the first node being related to at least one of the one or more words in the search string, wherein the ontology includes at least one node representing a concept and at least one node representing an attribute of the concept;

constructing a first database query based on the identified first node in the ontology, the first database query comprising one or more attributes associated with the first node, and a respective value, from the search string, for each of the one or more attributes;

after constructing the first database query, searching at least one database using the first database query;

identifying, based on a frequency of occurrence of a pair of user events, a second node in the ontology, the second node associated with the first node, the second additional node representing a concept not represented by the received search string, wherein a first user event of the pair of user events corresponds to the first node and a second user event of the pair of user events corresponds to the second node, and wherein for each occurrence of the pair of user events, the first user event and the second user event occur within a predetermined time period;

constructing a second database query based on the identified second;

after constructing the second database query, searching at least one database using the second database query; and

outputting results of the searching.

30. The computer readable storage medium of claim 29, wherein identifying the first node in an ontology comprises:

splitting the search string into one or more tokens, where each of the one or more tokens represents at least one of the one or more words;

parsing the one or more tokens, using the ontology; and

producing an interpretation of the search string as a result of the parsing.

31. The computer readable storage medium of claim 30, wherein parsing the one or more tokens comprises:

matching the one or more tokens to at least one node in the ontology.

32. The computer readable storage medium of claim 30, wherein producing an interpretation of the search string comprises:

producing a plurality of interpretations of the search string;

assigning a weight to each of the plurality of interpretations, the weight indicating a confidence that an associated one of the plurality of interpretations is correct; and

selecting a one of the plurality of interpretations with a highest weight.

33. The computer readable storage medium of claim 29, wherein the program is further configured to cause the at least one processor to perform the steps of:

identifying one or more missing search criteria in the search string; and

selecting a default value for the one or more missing search criteria from at least one of;

a user profile and a user search history.

34. The computer readable storage medium of claim 33, wherein the first database query further comprises an additional attribute having an additional value, wherein the additional value is the selected default value.

35. The computer readable storage medium of claim 29, wherein the ontology further comprises:

a plurality of links connecting nodes of the ontology with one another, each of the plurality of links representing a relation between nodes linked thereby.

36. The computer readable storage medium of claim 35, wherein the relation among nodes comprises an indication that one concept causes another concept.

37. The computer readable storage medium of claim 35, wherein at least one relation among nodes comprises an indication that concepts represented by the nodes tend to occur together.

38. The computer readable storage medium of claim 35, wherein at least one relation among nodes comprises an indication that one of the nodes represents at least one additional search criterion associated with a concept represented by another of the nodes.

39. The computer readable storage medium of claim 29, wherein the ontology is customized for a particular purpose.

40. The computer readable storage medium of claim 29, wherein the program is further configured to cause at least one processor to perform the step of:

augmenting the constructed database query by incorporating at least one additional attribute associated with at least one additional node linked to the identified first node.

41. The computer readable storage medium of claim 29, wherein the second database query comprises:

at least one attribute associated with the first node; and

a value, from the search string, of the at least one attribute.

42. The computer readable storage medium of claim 29, wherein the identified first node corresponds to a best weighted interpretation of user intent.

43. The computer readable storage medium of claim 29, wherein the program is further configured to cause at least one processor to perform the step of:

establishing at least one link between nodes based on observed behavior of at least one user.

44. The computer readable storage medium of claim 43, wherein establishing the at least one link between nodes comprises establishing a link between two nodes responsive to a degree of observed co-occurrence of identification of the two nodes in response to receiving user queries.

45. The computer readable storage medium of claim 29, wherein the ontology comprises an active ontology.

46. The computer readable storage medium of claim 29, wherein the program is further configured to cause at least one processor to perform the steps of:

generating a log of nodes identified as being related to a plurality of search strings received over a period of time;

determining co-occurrences among the logged nodes; and

augmenting the ontology to include links among nodes based on frequency of the determined co-occurrences.

47. The computer readable storage medium of claim 46, wherein generating a log comprises:

for each of a plurality of received search strings, storing a record comprising at least one of;

the search string, the identified node, the result, and a time stamp indicating a reception time of the search string.

48. The computer readable storage medium of claim 29, wherein the second node is associated with the first node based on a link between the first node and the second node.

49. The computer readable storage medium of claim 29, wherein the second node represents a concept not represented by the received search string, and wherein the second node is a concept node that does not match any of the words in the search string.

50. The computer readable storage medium of claim 29, wherein the first node and the second node are identified at substantially the same time.

51. The computer readable storage medium of claim 29, wherein the first node and the second node are identified prior to searching any database with either the first database query or the second database query.

52. The computer readable storage medium of claim 29, wherein the program is further configured to cause the at least one processor to perform the step of:

selecting at least a first database from a plurality of databases in accordance with a constraint defined in the first database query, wherein searching at least one database using the first database query comprises searching the selected at least a first database using the first database query.

53. The computer readable storage medium of claim 29, wherein:

searching at least one database using the first database query comprises searching a first database using the first database query to retrieve first results that satisfy one or more criteria defined in the first database query;

searching at least one database using the second database query comprises searching a second database using the second database query to retrieve second results that satisfy one or more criteria defined in the second database query, the second database is different from the first database; and

outputting results comprises outputting results based on the first result and the second results.

54. The computer readable storage medium of claim 29, wherein:

the first node in the ontology represents a first user intent of performing a first action;

the second node in the ontology represents a second user intent of performing a second action; and

the first node and the second node are directly connected by a link in the ontology, the link representing a causal relationship between the first action and the second action.

55. The computer readable storage medium of claim 29, wherein a keyword search with words from the user entered search string is not performed on the at least one database after receiving the user entered search string and prior to searching the at least one database using the first database query.

56. The computer readable storage medium of claim 29, wherein the first database query represents a user intent for the user entered search string.

57. A system for constructing a database query for searching at least one database, comprising:

an input device configured to receive a user entered search string, the search string comprising one or more words;

a processor, communicatively coupled to the input device, configured to perform the steps of;

identifying a first node in an ontology based on the one or more words of the search string, the first node being related to at least one of the one or more words in the search string, wherein the ontology includes at least one node representing a concept and at least one node representing an attribute of the concept;

constructing a first database query based on the identified first node in the ontology, the first database query one or more attributes associated with the first node, and a respective value, from the search string, for each of the one or more attributes;

identifying, based on a frequency of occurrence of a pair of user events, a second node in the ontology, the second node associated with the first node, the second node representing a concept not represented by the received search string, wherein a first user event of the pair of user events corresponds to the first node and a second user event of the pair of user events corresponds to the second node, and wherein for each occurrence of the pair of user events, the first user event and the second user event occur within a predetermined time period; and

constructing a second database query based on the identified second node representing a concept not represented by the received search string;

a search module, communicatively coupled to the processor, configured to perform the steps of;

after the first database query has been constructed, searching at least one database using the first database query; and

after the second database query has been constructed, searching at least one database using the second database query; and

an output device, communicatively coupled to the search module, configured to output results of the searching.

58. The system of claim 57, wherein the processor is configured to identify the first node in an ontology by:

splitting the search string into one or more tokens, where each of the one or more tokens represents at least one of the one or more words;

parsing the one or more tokens, using the ontology; and

producing an interpretation of the search string as a result of the parsing.

59. The system of claim 57, wherein the second database query comprises:

at least one attribute associated with the first node; and

a value, from the search string, of the at least one attribute.

60. The system of claim 57, wherein the processor is further configured to perform the steps of:

generating a log of nodes identified as being related to a plurality of search strings received over a period of time;

determining co-occurrences among the logged nodes; and

augmenting the ontology to include links among nodes based on frequency of the determined co-occurrences.

61. The system of claim 60, wherein at least one relation among nodes comprises an indication that concepts represented by the nodes tend to occur together.

62. The system of claim 60, wherein at least one relation among nodes comprises an indication that one of the nodes represents at least one additional search criterion associated with a concept represented by another of the nodes.

63. The system of claim 57, wherein the second node is associated with the first node based on a link between the first node and the second node.

64. The system of claim 57, wherein the second node represents a concept not represented by the received search string, and wherein the second node is a concept node that does not match any of the words in the search string.

65. The system of claim 57, wherein the first node and the second node are identified at substantially the same time.

66. The system of claim 57, wherein the first node and the second node are identified prior to searching any database with either the first database query or the second database query.

67. The system of claim 57, wherein the processor is further configured to perform the step of:

selecting at least a first database from a plurality of databases in accordance with a constraint defined in the first database query, wherein searching at least one database using the first database query comprises searching the selected at least a first database using the first database query.

68. The system of claim 57, wherein:

searching at least one database using the first database query comprises searching a first database using the first database query to retrieve first results that satisfy one or more criteria defined in the first database query;

searching at least one database using the second database query comprises searching a second database using the second database query to retrieve second results that satisfy one or more criteria defined in the second database query, the second database is different from the first database; and

outputting results comprises outputting results based on the first result and the second results.

69. The system of claim 57, wherein:

the first node in the ontology represents a first user intent of performing a first action;

the second node in the ontology represents a second user intent of performing a second action; and

the first node and the second node are directly connected by a link in the ontology, the link representing a causal relationship between the first action and the second action.

70. The system of claim 57, wherein a keyword search with words from the user entered search string is not performed on the at least one database after receiving the user entered search string and prior to searching the at least one database using the first database query.

71. The system of claim 57, wherein the first database query represents a user intent for the user entered search string.