Navigation tool for exploring a knowledge base

• US 7,231,384 B2
• Filed: 12/23/2002
• Issued: 06/12/2007
• 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
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): DANG, THANH HA T
• Application Number:
  US10/328,257
• Publication Number:
  US 20040083206A1
• Time in Patent Office: 1,632 Days
• Field of Search: 707/3, 707/4, 707/6
• US Class Current: 1/1
• 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 computer-implemented method comprising:

providing a search input visual display on a display device, the search input visual display comprising a search query area and a concept navigation area that is separate from the search query area, the concept navigation area comprising a first section and a second section separate from the first section;

receiving a search query that is entered by a user and displayed within the search query area;

performing a first search to identify any documents stored in a knowledge base that match the search query;

identifying any predefined concepts, from a predefined model of concepts, that are mentioned in at least one of any documents identified in the first search, wherein each of the predefined concepts from the model is a term or a phrase, and wherein the predefined model defines associations between different ones of the predefined concepts;

displaying, in the first section of the concept navigation area, any of the predefined concepts that were identified as being mentioned in any documents identified in the first search;

displaying, in the second section of the concept navigation area, any predefined concepts that the predefined model defines to be associated with at least one of any predefined concepts displayed in the first section of the concept navigation area;

receiving a user selection of one of the associated concepts displayed in the second section of the concept navigation area;

performing a second search to identify any documents stored in the knowledge base that match the search query and that mention the selected associated concept; and

displaying, in a search results display area, a list of any documents identified in the second search.

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:

provide a search input visual display on a display device, the search input visual display comprising a search query area and a concept navigation area that is separate from the search query area, the concept navigation area comprising a first section and a second section separate from the first section;

receive a search query that is entered by a user and displayed within the search query area;

perform a first search to identify any documents stored in a knowledge base that match the search query;

identify any predefined concepts, from a predefined model of concepts, that are mentioned in at least one of any documents identified in the first search, wherein each of the predefined concepts from the model is a term or a phrase, and wherein the predefined model defines associations between different ones of the predefined concepts;

display, in the first section of the concept navigation area, any of the predefined concepts that were identified as being mentioned in any documents identified in the first search;

display, in the second section of the concept navigation area, any predefined concepts that the predefined model defines to be associated with at least one of any predefined concepts displayed in the first section of the concept navigation area;

receive a user selection of one of the associated concepts displayed in the second section of the concept navigation area;

perform a second search to identify any documents stored in the knowledge base that match the search query and that mention the selected associated concept; and

display, in a search results display area, a list of any documents identified in the second search.

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 arc 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 model of concepts each of which appears in at least one document stored in the knowledge base and is a term or phrase;

a display screen including a concept navigation area with 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;

provide a search input visual display on a display device, the search input visual display comprising a search query area and a concept navigation area that is separate from the search query area, the concept navigation area comprising a first section and a second section separate from the first section;

receive a search query that is entered by a user and displayed within the search query area;

perform a first search to identify any documents stored in a knowledge base that match the search query;

identify any predefined concepts, from a predefined model of concepts, that are mentioned in at least one of any documents identified in the first search, wherein each of the predefined concepts from the model is a term or a phrase, and wherein the predefined model defines associations between different ones of the predefined concepts;

cause the display screen to display, in the first section of the concept navigation area, any of the predefined concepts that were identified as being mentioned in any documents identified in the first search;

cause the display screen to display, in the second section of the concept navigation area, any predefined concepts that the predefined model defines to be associated with at least one of any predefined concepts displayed in the first section of the concept navigation area;

receive a user selection of one of the associated concepts displayed in the second section of the concept navigation area;

perform a second search to identify any documents stored in the knowledge base that match the search query and that mention the selected associated concept; and

display, in a search results display area, a list of any documents identified in the second search.

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 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.

48. 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.

49. 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.

50. The system of claim 49 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.

51. 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.

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 computer-implemented method comprising:

identifying concepts that are mentioned in electronic documents stored in a knowledge base, each of the concepts being a term or phrase;

generating a matrix to reflect co-occurrence frequencies of concepts appearing in the electronic 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 electronic 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.

65. The method of claim 64 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.

66. The method of claim 65 including determining the correlation based on an edge weight of the hypergraph.

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

68. The method of claim 67 including storing strengths of links between different concepts.

69. 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, each of the concepts being a term or phrase;

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.

70. The article of claim 69 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.

71. The article of claim 70 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.

72. The article of claim 70 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.

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