Navigation tool for exploring a knowledge base

• US 20040083206A1
• Filed: 12/23/2002
• Published: 04/29/2004
• Est. Priority Date: 10/25/2002
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Gong, Huiling, Wu, Yuh-Cherng
• Granted Patent: US 7,231,384 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/3323 using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The disclosure relates to a system that allows a user to enter a search query, to explore a knowledge base through a hierarchical model of concepts each of which is mentioned in one or more documents stored in the knowledge base, and to refine the search query based on a displayed portion of the hierarchical model.

Claims

1. A method comprising:

displaying, in response to receiving a search query, one or more concepts from a hierarchical model of concepts, wherein each concept in the hierarchical model is mentioned in at least one document stored in a knowledge base, and wherein the one or more concepts match the search query and are displayed on a first section of a display; and

displaying, on an area of the display other than the first section, concepts from the hierarchical model that are associated with the one or more concepts displayed in the first section.

2. The method of claim 1 including:

displaying the one or more concepts that match the search query in a center area; and

displaying the associated concepts at distal ends of spokes connected to the center area.

3. The method of claim 1 including:

adding one or more of the associated concept to the first section of the display in response to user input; and

displaying a list of one or more documents or links to documents each of which mentions at least one of the concepts in the first section of the display.

4. The method of claim 3 including adding an associated concept to the first section of the display in response to the user'"'"'s dragging and dropping that associated concept into the first section using a user input device.

5. The method of claim 1 including:

removing a concept from the first section of the display in response to user input; and

displaying a list of one or more documents or links to documents each of which mentions at least one concept in the first section of the display.

6. The method of claim 5 including removing a concept from the first section of the display in response to the user'"'"'s dragging and dropping that concept out of the first section using a user input device.

7. The method of claim 1 including displaying an indication of a degree of association between each associated concept and at least one concept listed in the first section of the display.

8. The method of claim 1 including identifying which associated concepts are associated with each concept listed in the first section of the display.

9. The method of claim 1 including:

displaying a different view of the hierarchical model of concepts in response to user input specifying one of the displayed associated concepts, wherein, in the different view, only the specified concept appears in the first section of the display; and

providing a list of one or more documents or links to documents each of which mentions the specified concept appearing in the first section of the display.

10. The method of claim 1 including:

displaying a different view of the hierarchical model of concepts in response to user input specifying one of the displayed associated concepts, wherein, in the different view, the specified concept appears in the first section of the display along with one or more concepts previously specified by the user to be retained in future views of the hierarchical concept model; and

displaying a list of one or more documents or links to documents each of which mentions at least one of the concepts in the first section of the display.

11. The method of claim 1 including displaying a different view of the hierarchical model of concepts in response to user input, wherein, in the different view, a different level of granularity is displayed for a concept specified by the user.

12. The method of claim 11 including displaying a finer level of granularity of detail for the specified concept.

13. The method of claim 11 including displaying a coarser level of granularity of detail for the specified concept.

14. The method of claim 1 including displaying a description of a particular displayed concept in response to user input specifying the particular displayed concept.

15. The method of claim 1 including displaying, in response to user input, additional concepts that are associated with the concepts listed in the first section of the display.

16. The method of claim 1 including providing, in response to user input, a list of historical views of the hierarchical concept model previously displayed.

17. The method of claim 16 including displaying a new view of the hierarchical concept model that combines a plurality of historical views specified by the user, wherein, in the new view, concepts previously listed in the first section of the display for at least one of the specified historical views are listed in the first section of the display, and associated concepts are listed elsewhere in the display.

18. The method of claim 16 including displaying one of the historical views specified by the user.

19. The method of claim 1 including displaying, in response to user input, a view of the hierarchical concept model previously displayed to the user.

20. The method of claim 1 including:

providing, in response to user input, a list of concepts previously listed in the first section of the display for different views of the hierarchical concept model; and

displaying a new view of the hierarchical concept model based on a combination of concepts specified by the user from the list of concepts previously listed in the first section, wherein, in the new view, the specified concepts are listed in the first section of the display, and concepts that are associated with the specified concepts are listed elsewhere in the display.

21. The method of claim 1 including displaying a list of one or more documents or links to documents each of which mentions at least one of the concepts in the first section of the display.

22. An article comprising a machine-readable medium that stores machine-executable instructions that when applied to the machine, cause the machine to:

display, in response to receiving a search query, one or more concepts from a hierarchical model of concepts, wherein each concept in the hierarchical model is mentioned in at least one document stored in a knowledge base, and wherein the one or more concepts match the search query and are displayed on a first section of a display; and

display, on an area of the display other than the first section, concepts from the hierarchical model that are associated with the one or more concepts displayed in the first section.

23. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to:

display the one or more concepts that match the search query in a center area; and

display the associated concepts at distal ends of spokes connected to the center area.

24. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to:

add an associated concept to the first section of the display in response to user input; and

display a list of one or more documents or links to documents each of which mentions at least one concept in the first section of the display.

25. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to add an associated concept to the first section of the display in response to the user'"'"'s dragging and dropping that associated concept into the first section using a user input device.

26. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to:

remove a concept from the first section of the display in response to user input; and

display a list of one or more documents or links to documents each of which mentions at least one concept in the first section of the display.

27. The article of claim 26 including machine-executable instructions that, when applied to the machine, cause the machine to remove a concept from the first section of the display in response to the user'"'"'s dragging and dropping that concept out of the first section using a user input device.

28. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to display an indication of a degree of association between each associated concept and at least one concept listed in the first section of the display.

29. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to identify which associated concepts are associated with each concept listed in the first section of the display.

30. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to:

display a different view of the hierarchical model of concepts in response to user input specifying one of the displayed associated concepts, wherein, in the different view, only the specified concept appears in the first section of the display; and

provide a list of one or more documents or links to documents each of which mentions the specified concept in the first section of the display.

31. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to:

display a different view of the hierarchical model of concepts in response to user input specifying one of the displayed associated concepts, wherein, in the different view, the specified concept appears in the first section of the display along with one or more concepts previously specified by the user to be retained in future views of the hierarchical concept model; and

display a list of one or more documents or links to documents each of which mentions at least one of the concepts in the first section of the display.

32. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to display a different view of the hierarchical model of concepts in response to user input, wherein, in the different view, a different level of granularity is displayed for a concept specified by the user.

33. The article of claim 32 including machine-executable instructions that, when applied to the machine, cause the machine to display a finer level of granularity of detail for the specified concept.

34. The article of claim 32 including machine-executable instructions that, when applied to the machine, cause the machine to display a coarser level of granularity of detail for the specified concept.

35. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to display a description of a particular displayed concept in response to user input specifying the particular displayed concept.

36. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to display, in response to user input, additional concepts associated with the concepts in the first section of the display.

37. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to provide, in response to user input, a list of historical views of the hierarchical concept model previously displayed.

38. The article of claim 37 including machine-executable instructions that, when applied to the machine, cause the machine to display a new view of the hierarchical concept model that combines a plurality of historical views specified by the user, wherein, in the new view, concepts previously listed in the first section of the display for at least one of the specified historical views are listed in the first section of the display, and associated concepts are listed elsewhere in the display.

39. The article of claim 37 including machine-executable instructions that, when applied to the machine, cause the machine to display one of the historical views specified by the user.

40. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to display, in response to user input, a view of the hierarchical concept model previously displayed to the user.

41. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to:

provide, in response to user input, a list of concepts previously listed in the first section of the display for different views of the hierarchical concept model; and

display a new view of the hierarchical concept model based on a combination of concepts specified by the user from the list of concepts previously listed in the first section, wherein, in the new view, the specified concepts are listed in the first section of the display, and concepts that are associated with the specified concepts are listed elsewhere in the display.

42. The article of claim 22 including machine-executable instructions that, when applied to the machine, cause the machine to display a list of one or more documents or links to documents each of which mentions at least one of the concepts in the first section of the display.

43. A system comprising:

a knowledge base storing documents;

memory storing a hierarchical model of concepts each of which appears in at least one document stored in the knowledge base;

a display screen including a first section;

a user input device; and

circuitry coupled to the knowledge base, the memory, the display screen and the user input device to;

cause the display screen to display, in response to receiving a search query, one or more concepts from the hierarchical model of concepts, wherein the one or more concepts match the search query and are displayed on the first section of the display screen; and

cause the display screen to display, on an area of the display screen other than the first section, concepts from the hierarchical model that are associated with the one or more concepts displayed in the first section.

44. The system of claim 43 including circuitry to:

cause the display screen to display the one or more concepts that match the search query in a center area; and

cause the display screen to display the associated concepts at distal ends of spokes connected to the center area.

45. The system of claim 43 including circuitry to:

add an associated concept to the first section of the display in response to user input; and

cause the display screen to display a list of one or more documents or links to documents each of which mentions at least one concept in the first section of the display screen.

46. The system of claim 45 including circuitry to add an associated concept to the first section of the display in response to the user'"'"'s dragging and dropping that associated concept into the first section using the user input device.

47. The system of claim 43 including circuitry to:

remove a concept from the first section of the display in response to user input; and

cause the display screen to display a list of one or more documents or links to documents each of which mentions at least one concept in the first section of the display screen.

48. The system of claim 47 including circuitry to remove a concept from the first section of the display in response to the user'"'"'s dragging and dropping that concept out of the first section of the display screen using the user input device.

49. The system of claim 45 including circuitry to cause the display screen to display a degree of association between an associated concept and a concept listed in the first section of the display in response to user input.

50. The system of claim 43 including circuitry to cause the display screen to display an identification of which associated concepts are associated with each concept listed in the first section of the display screen.

51. The system of claim 45 including circuitry to:

cause the display screen to display a different view of the hierarchical model of concepts in response to user input specifying one of the displayed associated concepts, wherein, in the different view, only the specified concept appears in the first section of the display; and

cause the display screen to display a list of one or more documents or links to documents each of which mentions the specified concept appearing in the first section of the display screen.

52. The system of claim 43 including circuitry to:

cause the display screen to display a different view of the hierarchical model of concepts in response to user input specifying one of the displayed associated concepts, wherein, in the different view, the specified concept appears in the first section of the display along with one or more concepts previously specified by the user to be retained in future views of the hierarchical concept model; and

cause the display screen to display a list of one or more documents or links to documents each of which mentions at least one of the concepts in the first section of the display screen.

53. The system of claim 43 including circuitry to cause the display screen to display a different view of the hierarchical model of concepts in response to user input, wherein, in the different view, a different level of granularity is displayed for a concept specified by the user.

54. The system of claim 53 including circuitry to cause the display screen to display a finer level of granularity of detail for the specified concept in response to user input.

55. The system of claim 53 including circuitry to cause the display screen to display a coarser level of granularity of detail for the specified concept in response to user input.

56. The system of claim 43 including circuitry to cause the display screen to display a description of a particular displayed concept in response to user input specifying the particular displayed concept.

57. The system of claim 43 including circuitry to cause the display screen to display, in response to user input, additional concepts associated with the concepts listed in the first section of the display screen.

58. The system of claim 43 including circuitry to cause the display screen to display, in response to user input, a list of historical views of the hierarchical concept model previously displayed.

59. The system of claim 58 including circuitry to cause the display screen to display a new view of the hierarchical concept model that combines a plurality of historical views specified by the user, wherein, in the new view, concepts previously listed in the first section of the display screen for at least one of the specified historical views are listed in the first section of the display screen, and associated concepts are listed elsewhere in the display screen.

60. The system of claim 58 including circuitry to cause the display screen to display one of the historical views specified by the user.

61. The system of claim 43 including circuitry to cause the display screen to display, in response to user input, a view of the hierarchical concept model previously displayed to the user.

62. The system of claim 43 including circuitry to:

cause the display screen to display, in response to user input, a list of concepts previously listed in the first section of the display for different views of the hierarchical concept model; and

cause the display screen to display a new view of the hierarchical concept model based on a combination of concepts specified by the user from the list of concepts previously listed in the first section, wherein, in the new view, the specified concepts are listed in the first section of the display, and concepts that are associated with the specified concepts are listed elsewhere in the display.

63. The system of claim 43 including circuitry to display a list of one or more documents or links to documents each of which mentions at least one of the concepts in the first section of the display screen.

64. A method comprising:

exploring on a display screen a hierarchical model of concepts that are mentioned in documents stored in a knowledge base, the hierarchical model including concepts and concept clusters, wherein each concept cluster is represented by a concept in that cluster;

selecting one or more displayed concepts from the hierarchical model for inclusion in a refined search query; and

viewing a list of documents or links to documents each of which mentions at least one of the selected concepts.

65. The method of claim 64 including navigating horizontally in a particular layer of the hierarchical model of concepts.

66. The method of claim 64 including navigating vertically among different layers of the hierarchical model of concepts.

67. A method comprising:

identifying concepts that are mentioned in documents stored in a knowledge base;

generating a matrix to reflect co-occurrence frequencies of concepts appearing in the documents;

generating association rules based on the co-occurrence frequencies, wherein the association rules are indicative of frequencies with which specified groups of concepts appear in the same document;

converting the association rules to an undirected hypergraph;

partitioning the undirected hypergraph into clusters of concepts, wherein each cluster is represented by one or more characteristic concepts in that cluster;

taking snapshots of the hypergraph during the partitioning; and

storing a three-dimensional hierarchical model of the concepts based on the snapshots.

68. The method of claim 67 including, for each cluster, selecting one or more characteristic concepts having a high correlation with other concepts in the same cluster as representatives of that cluster.

69. The method of claim 68 including determining the correlation based on an edge weight of the hypergraph.

70. The method of claim 68 storing relationships between concepts at the same level and different levels of the hierarchical concept model.

71. The method of claim 70 including storing strengths of links between different concepts.

72. An article comprising a machine-readable medium that stores machine-executable instructions that when applied to the machine, cause the machine to:

identify concepts that are mentioned in documents stored in a knowledge base;

generate a matrix to reflect co-occurrence frequencies of concepts appearing in the documents;

generate association rules based on the co-occurrence frequencies, wherein the association rules are indicative of frequencies with which specified groups of concepts appear in the same document;

convert the association rules to an undirected hypergraph;

partition the undirected hypergraph into clusters of concepts, wherein each cluster is represented by a concept in that cluster;

take snapshots of the clusters during the partitioning; and

store a three-dimensional hierarchical model of the concepts based on the snapshots.

73. The article of claim 72 including machine-executable instructions that, when applied to the machine, cause the machine to select, for each cluster, one or more characteristic concepts having a high correlation with other concepts in the same cluster as representatives of that cluster.

74. The article of claim 73 including machine-executable instructions that, when applied to the machine, cause the machine to determine the correlation based on an edge weight of the hypergraph.

75. The article of claim 73 including machine-executable instructions that, when applied to the machine, cause the machine to store relationships between concepts at the same level and different levels of the hierarchical concept model.

76. The article of claim 75 including machine-executable instructions that, when applied to the machine, cause the machine to store strengths of links between different concepts.