Intelligent exploration through multiple hierarchies using entity relevance

• US 6,460,025 B1
• Filed: 07/27/1999
• Issued: 10/01/2002
• Est. Priority Date: 07/27/1999
• Status: Expired due to Term

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Fohn, Steffen Michael, Willenborg, Donald Carl, Greef, Arthur Reginald
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Holmes, Michael B.
• Application Number:
  US09/361,756
• Time in Patent Office: 1,162 Days
• Field of Search: 716/1, 717/1, 706/45
• US Class Current: 706/45
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957

Abstract

A method, system, and computer readable code for improving user exploration (i.e. navigation and browsing) through hierarchies of information. Entity relevance is calculated for the entities in the hierarchies, and this information is used to guide the user in his exploration. Two types of entity relevance are used, structural relevance and state relevance. Structural relevance is preferably pre-computed, being static in nature. State relevance is dynamically computed, as the user selects nodes or categories during exploration. Each selection serves to further constrain the solution space. Entities are determined to be strongly relevant, weakly relevant, or irrelevant for the current solution space. Node feasibility is also dynamically calculated, and provides a forward-looking indication of which nodes can be selected while still remaining consistent with the current solution space.

Claims

1. A computer program product on a computer-readable medium in a computing environment for improving user exploration through multiple hierarchies of information, comprising:

computer-readable program code means for computing a structural relevance for each of a root node and one or more intermediate nodes in each of one or more category hierarchies, each of said category hierarchies comprising said root node, said one or more intermediate nodes, and one or more leaf nodes, wherein each of said root nodes and said intermediate nodes corresponds to a category in said hierarchy and wherein each of said leaf nodes corresponds to an entity categorized by said hierarchy;

computer-readable program code means for enabling a user of said computer program product to select a particular one of said root nodes or said intermediate nodes;

computer-readable program code means, responsive to operation of said computer-readable program code means for enabling, for computing a state relevance reflecting said selection;

computer-readable program code means, responsive to operation of said computer-readable program code means for computing said state relevance, for computing a node feasibility reflecting said state relevance; and

computer-readable program code means for displaying a graphical representation of said computed node feasibility to guide said user in exploring said one or more category hierarchies.

2. The computer program product for improving user exploration through multiple hierarchies of information according to claim 1, wherein said computer-readable program code means for computing said structural relevance further comprises computer-readable program code means for determining a static set of strongly relevant, weakly relevant, irrelevant, and relevant ones of said entities for each of said root nodes and said intermediate nodes.

3. The computer program product for improving user exploration through multiple hierarchies of information according to claim 2, wherein said computer-readable program code means for computing said state relevance further comprises computer-readable program code means for determining a dynamic set of strongly relevant, weakly relevant, irrelevant, and relevant ones of said entities based upon a previous state of said dynamic set and said static set for said selected node.

4. The computer program product for improving user exploration through multiple hierarchies of information according to claim 1, wherein said computer-readable program code means for computing said node feasibility further comprises computer-readable program code means for determining a feasible or non-feasible status of each of said root nodes and said intermediate nodes which have not yet been selected.

5. The computer program product for improving user exploration through multiple hierarchies of information according to claim 4, wherein said computer-readable program code means for determining said feasible or non-feasible status determines said status to be feasible when said static set of relevant ones for said selected node has at least one entity in common with said dynamic set of relevant ones, and determines said status to be infeasible otherwise.

6. A system in a computing environment for improving user exploration through multiple hierarchies of information, comprising:

means for computing a structural relevance for each of a root node and one or more intermediate nodes in each of one or more category hierarchies, each of said category hierarchies comprising said root node, said one or more intermediate nodes, and one or more leaf nodes, wherein each of said root nodes and said intermediate nodes corresponds to a category in said hierarchy and wherein each of said leaf nodes corresponds to an entity categorized by said hierarchy;

means for enabling a user of said system to select a particular one of said root nodes or said intermediate nodes;

means, responsive to operation of said means for enabling, for computing a state relevance reflecting said selection;

means, responsive to operation of said means for computing said state relevance, for computing a node feasibility reflecting said state relevance; and

means for displaying a graphical representation of said computed node feasibility to guide said user in exploring said one or more category hierarchies.

7. The system for improving user exploration through multiple hierarchies of information according to claim 6, wherein said means for computing said structural relevance further comprises means for determining a static set of strongly relevant, weakly relevant, irrelevant, and relevant ones of said entities for each of said root nodes and said intermediate nodes.

8. The system for improving user exploration through multiple hierarchies of information according to claim 7, wherein said means for computing said state relevance further comprises means for determining a dynamic set of strongly relevant, weakly relevant, irrelevant, and relevant ones of said entities based upon a previous state of said dynamic set and said static set for said selected node.

9. The system for improving user exploration through multiple hierarchies of information according to claim 6, wherein said means for computing said node feasibility further comprises means for determining a feasible or non-feasible status of each of said root nodes and said intermediate nodes which have not yet been selected.

10. The system for improving user exploration through multiple hierarchies of information according to claim 9, wherein said means for determining said feasible or non-feasible status determines said status to be feasible when said static set of relevant ones for said selected node has at least one entity in common with said dynamic set of relevant ones, and determines said status to be infeasible otherwise.

11. A method for improving user exploration through multiple hierarchies of information in a computing environment, comprising the steps of:

computing a structural relevance for each of a root node and one or more intermediate nodes in each of one or more category hierarchies, each of said category hierarchies comprising said root node, said one or more intermediate nodes, and one or more leaf nodes, wherein each of said root nodes and said intermediate nodes corresponds to a category in said hierarchy and wherein each of said leaf nodes corresponds to an entity categorized by said hierarchy;

enabling a user of said method to select a particular one of said root nodes or said intermediate nodes;

computing a state relevance reflecting said selection, responsive to operation of said enabling step;

computing a node feasibility reflecting said state relevance, responsive to operation of said step of computing said state relevance; and

displaying a graphical representation of said computed node feasibility to guide said user in exploring said one or more category hierarchies.

12. The method for improving user exploration through multiple hierarchies of information according to claim 11, wherein said step of computing said structural relevance further comprises the step of determining a static set of strongly relevant, weakly relevant, irrelevant, and relevant ones of said entities for each of said root nodes and said intermediate nodes.

13. The method for improving user exploration through multiple hierarchies of information according to claim 12, wherein said step of computing said state relevance further comprises the step of determining a dynamic set of strongly relevant, weakly relevant, irrelevant, and relevant ones of said entities based upon a previous state of said dynamic set and said static set for said selected node.

14. The method for improving user exploration through multiple hierarchies of information according to claim 11, wherein said step of computing said node feasibility further comprises the step of determining a feasible or non-feasible status of each of said root nodes and said intermediate nodes which have not yet been selected.

15. The method for improving user exploration through multiple hierarchies of information according to claim 14, wherein said step of determining said feasible or non-feasible status determines said status to be feasible when said static set of relevant ones for said selected node has at least one entity in common with said dynamic set of relevant ones, and determines said status to be infeasible otherwise.

16. A method of guiding user exploration of hierarchically-structured information in a computing environment, comprising steps of:

programmatically analyzing a category hierarchy, said hierarchy comprising a root node, one or more intermediate nodes, and one or more leaf nodes, wherein each of said root nodes and said intermediate nodes corresponds to a category in said hierarchy and wherein each of said leaf nodes corresponds to an entity categorized by said hierarchy, to determine how directly the root node and the one or more intermediate nodes are related to the entities at the leaf nodes;

programmatically determining, responsive to a user selecting to navigate from said root node to one of said intermediate nodes, or from one of said intermediate nodes to another of said intermediate nodes, which of said entities remains a feasible selection for a navigation path which comprises said nodes selected for said navigating; and

displaying, responsive to said programmatically determining step, a graphical representation of said entities that remain feasible selections.

17. The method according to claim 16, wherein said category hierarchy represents an electronic catalog and wherein said entities are products available from said electronic catalog.

18. The method according to claim 16, wherein said category hierarchy represents an electronic catalog and wherein said entities are parts available from said electronic catalog.

19. The method according to claim 16, wherein said category hierarchy represents an on-line auction service and wherein said entities are products being offered at auction through said on-line auction service.