Method and apparatus for construction and use of concept knowledge base

• US 20070282826A1
• Filed: 06/06/2006
• Published: 12/06/2007
• Est. Priority Date: 06/06/2006
• Status: Active Grant

• Current Assignee: Blackbird Tech LLC
• Original Assignee: University of Regina
• Inventors: Hoeber, Orland Harold, Yang, Xue-Dong, Yao, Yiyu
• Granted Patent: US 7,752,243 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A data structure, apparatuses and methods for expanding a search query to be used by a web search engine is provided. The search query is expanded by accessing a concept knowledge base data structure having concept data objects and term data objects with each term data object defining a term and associated with at least one of the concept data objects. Search terms making up the search query are matched to term data objects and a concept set is generated containing concept data objects associated with the term data objects. A second set of term data objects are generated by using the concept data objects to locate term data objects associated with the concept data objects. A user can then select one of the term data objects in the second set to expand the user'"'"'s search query.

Claims

1. A memory for storing data for access by an application program being executed on a data processing system, comprising:

a data structure stored in said memory, said data structure including information resident in a database used by said application program and including;

a plurality of concept data objects stored in the memory, each of said concept data objects containing information related to a concept; and

a plurality of term data objects stored in the memory, each term data object containing information related to a term;

wherein each of the term data objects is associated with one or more of the concept data objects and the association has an assigned weight.

2. The memory of claim 1 wherein each association between one of the concept data objects and one of the term data objects has an assigned weight.

3. The memory of claim 2 wherein the data structure comprises a plurality of edge data objects, each edge data object defining an association between one of the concept data objects and one of the term data objects and the edge data object containing the assigned weight.

4. A method of automatically generating a concept knowledge base data structure from a plurality of computer readable documents related to a knowledge field, the method comprising:

determining a plurality of concepts and for each concept creating a concept data object corresponding to the concept;

for each concept, analyzing at least one computer readable document describing the concept and selecting terms in the computer readable document; and

for each selected term, creating a term data object associated with the concept data object.

5. The method of claim 4 further comprising for each selected term determining a weight indicating the relevance of the association between the concept node and the term node.

6. The method of claim 5 wherein each weight is determined by tallying the occurrence of the selected term in the at least one document describing a concept.

7. The method of claim 6 wherein the weight is determined by averaging a frequency term by the frequency of the other selected terms in the document.

8. The method of claim 6 wherein each the weight is normalized.

9. The method of claim 4 wherein an edge data object is created for each association between one of the term data objects and one of the concept data objects.

16. A computer readable memory having recorded thereon statements and instructions for execution by a data processing system to carry out the method of claim 4.

10. A data processing system for automatically generating a concept knowledge base data structure from a plurality of computer readable documents related to a knowledge field, the data processing system comprising:

at least one processing unit;

at least one memory storage device operatively coupled to the processing unit; and

a program module stored in the at least one memory storage device operative for providing instructions to the at least one processing unit, the at least one processing unit responsive to the instructions of the program module, the program module operative for;

determining a plurality of concepts and for each concept creating a concept data object corresponding to the concept on the at least one memory storage device;

for each concept, analyzing at least one computer readable document describing the concept and selecting terms in the computer readable document; and

for each selected term, creating a term data object on the at least one memory storage device and associating the term data object with the concept data object.

11. The data processing system of claim 10 wherein the program module is operative for calculating a weight for each association between a term data object and a concept data object, the weight indicating the relevance of the term data object to the concept data object.

12. The data processing system of claim 11 wherein each weight of an association is determined by tallying the occurrence of the selected term in the at least one document describing a concept.

13. The data processing system of claim 11 wherein each weight of an association is determined by averaging a frequency term by the frequency of the other selected terms in the document.

14. The data processing system of claim 11 wherein each weight is normalized.

15. The data processing system of claim 10 wherein an edge data object is created on the at least one memory storage device for each association between one of the term data objects and one of the concept data objects.

17. A method of expanding a search query comprising:

using a search query comprising a plurality of search terms, accessing a concept knowledge base data structure having a plurality of concept data objects and a plurality of term data objects, each term data object defining a term and associated with at least one of the concept data objects;

generating a first term set containing term data objects from the concept knowledge base data structure wherein each term data object in the first term set matches one or more of the search terms;

generating a concept set containing concept data objects from the concept knowledge base data structure wherein each concept data object in the concept set is associated with one or more of the term data objects in the first term set;

generating a second term set containing term data objects from the concept knowledge base data structure wherein each term data object in the second term set is associated with one ore more of the concept data objects in the concept set; and

in response to selecting one of the term data objects in the second term set, adding the term contained in the selected term data object to the search query.

18. The method of claim 17 wherein each concept data object contained in the concept set is associated with at least one of the term data objects in the first term set by a weight greater than a weight threshold.

19. The method of claim 18 wherein each concept data object contained in the concept set has a term ratio greater than a term ratio threshold wherein the term ratio is calculated by determining the ratio of all of the term data objects in the first term set and the number of term data objects in the first term set that the concept data object has an association with greater than the weight threshold.

20. The method of claim 17 wherein each concept data objects contained in the concept set is associated with at least one of the term data objects in the first term set with a weight greater than a first weight threshold and each term data object in the second term set is associated with at least one of the concept data objects in the concept set by a weight greater than a second weight threshold.

21. The method of claim 17 comprising generating a visual representation by graphically representing the term data objects in the first term set and the term data objects in the second term set as term nodes and the concept data objects in the concept set as concept nodes and wherein a user can select a term data object in the second term set to add the term contained in the selected term data object to the search query by selecting the term node corresponding to the selected term data object.

22. The method of claim 21 comprising graphically representing an association between a term data object and a concept data object by displaying a line connecting the term node, representing the term data object, and the concept node, representing the concept data object.

23. The method of claim 22 wherein a weight assigned to the association is represented by a distance between the term node and the concept node.

24. The method of claim 21 further comprising, in response to a user selecting one of the concept nodes in the visual representation, removing the selected concept node and any term nodes representing term data objects associated only with a concept node represented by the selected concept node from the visual representation.

25. The method of claim 21 further comprising requesting search results from a search engine using the search query and displaying the search results to the on the display device in conjunction with the visual representation.

46. A computer readable memory having recorded thereon statements and instructions for execution by a data processing system to carry out the method of claim 17.

26. A data processing system for expanding a search query, the data processing system comprising:

at least one processing unit;

at least one memory storage device operatively coupled to the processing unit and containing a concept knowledge base data structure, the concept knowledge base data structure including;

a plurality of concept data objects; and

a plurality of term data objects, each term data object defining a term and associated with at least one of the concept data objects; and

a program module stored in the at least one memory storage device operative for providing instructions to the at least one processing unit, the at least one processing unit responsive to the instructions of the program module, the program module operative for;

using a search query containing one or more search terms, generating a first term set containing term data objects from the concept knowledge base data structure wherein each term data object in the first term set matches one or more of the search terms;

generating a concept set containing concept data objects from the concept knowledge base data structure wherein each concept data object in the concept set is associated with one or more of the term data objects in the first term set;

generating a second term set containing term data objects from the concept knowledge base data structure wherein each term data object in the second term set is associated with one or more of the concept data objects in the concept set; and

in response to selecting one of the term data objects in the second term set, adding the term contained in the selected term data object to the search query.

27. The data processing system of claim 26 wherein each concept data object contained in the concept set is associated with at least one of the term data objects in the first term set by a weight greater than a predetermined weight threshold.

28. The data processing system of claim 27 wherein each concept data object contained in the concept set has a term ratio greater than a term ratio threshold wherein the term ratio is calculated by determining the ratio of all of the term data objects in the first term set and the number of term data objects in the first term set that the concept data object has an association with greater than the weight threshold.

29. The data processing system of claim 26 wherein each concept data objects contained in the concept set is associated with at least one of the term data objects in the first term set with a weight greater than a first weight threshold and each term data object in the second term set is associated with at least one of the concept data objects in the concept set by a weight greater than a second weight threshold.

30. The data processing system of claim 26 wherein the data processing system comprises a display device operatively coupled to the data processing system and the program module is operative to direct the processing unit to display a visual representation on the display device by graphically representing the term data objects in the first term set and the term data objects in the second term set as term nodes and the concept data objects in the concept set as concept nodes.

31. The data processing system of claim 30 wherein an association between a term data object and a concept data object is graphically represented on the visual representation by a line connecting the term node representing the term data object, and the concept node representing the concept data object.

32. The data processing system of claim 31 wherein a weight assigned to the association is represented by a distance between the term node and the concept node.

33. The data processing system of claim 32 wherein the term nodes corresponding to the term data objects in the first term set are visually distinctive from the term nodes corresponding to the term data objects in the second term set.

34. The data processing system of claim 33 wherein the term nodes corresponding to the term data objects in the first term set are displayed in a first color and the term nodes corresponding to the term data objects in the second term set are a second color.

35. The data processing system of claim 30 wherein the data processing system further comprises an input device and a term data object is selected by a user using the input device to indicate the term node corresponding to the term data object.

36. The data processing system of claim 30 wherein the program module is operative for, in response to a user selecting one of the concept nodes in the visual representation, removing the selected concept node and any term nodes representing term data objects associated only with a concept node represented by the selected concept node from the visual representation.

37. The data processing system of claim 30 wherein the input device is a computer mouse and the user uses the mouse to select the term node corresponding to the term data object.

38. The data processing system of claim 30 wherein the program modules is operative for:

requesting search results from a search engine and displaying the search results on the display device in conjunction with the visual representation.

39. The data processing system of claim 26 wherein the data processing system is operatively connectable to a remote device and wherein a user of the remote device inputs the search query to the data processing system and wherein the program module is operative to direct the processing unit to communicate with the remote device and display a visual representation on the remote device by graphically representing the term data objects in the first term set and the term data objects in the second term set as term nodes and the concept data objects in the concept set as concept nodes.

40. The data processing system of claim 39 wherein an association between a term data object and a concept data object is graphically represented on the visual representation by a line connecting the term node representing the term data object, and the concept node representing the concept data object.

41. The data processing system of claim 40 wherein a weight assigned to the association is represented by a distance between the term node and the concept node.

42. The data processing system of claim 41 wherein the term nodes corresponding to the term data objects in the first term set are visually distinctive from the term nodes corresponding to the term data objects in the second term set.

43. The data processing system of claim 42 wherein the term nodes corresponding to the term data objects in the first term set are displayed in a first color and the term nodes corresponding to the term data objects in the second term set are a second color.

44. The data processing system of claim 39 wherein the program module is operative for, in response to a user selecting one of the concept nodes in the visual representation, removing the selected concept node and any term nodes representing term data objects associated only with a concept node represented by the selected concept node from the visual representation.

45. The data processing system of claim 39 wherein the program modules is operative for:

requesting search results from a search engine and displaying the search results on the remote device in conjunction with the visual representation.