System and method for browsing hierarchically based node-link structures based on an estimated degree of interest

• US 6,944,830 B2
• Filed: 12/21/2000
• Issued: 09/13/2005
• Est. Priority Date: 12/21/2000
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Card, Stuart K., Nation, David A.
• Primary Examiner(s): Cabeca, John
• Assistant Examiner(s): BASOM, BLAINE T
• Application Number:
  US09/747,634
• Publication Number:
  US 20030085931A1
• Time in Patent Office: 1,727 Days
• Field of Search: 345/853, 345/854, 345/855, 345/640, 345/440, 707/102, 707/104.1, 715/514, 715/767, 715/783, 715/788, 715/800, 715/804, 715/810, 715/815, 715/818, 715/823, 715/835, 715/968
• US Class Current: 715/853
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

Method and system to enable a user to view large collections of hierarchically linked information on a computer based display. A tree structure visualization is created which presents a representation of the complete collection of information on the display. The visualization fits completely within a fixed area of the computer based display, negating the need to scroll information into the display area. The visualization is based on identified focus nodes and through calculation of a Degree of Interest (DOI) for each of the nodes based in the structure. Layout and presentation of the visualization structure is based on the DOI values in combination with considerations of available display space. A user may dynamically manipulate views of the structure by selecting one or more focus nodes, thus causing a recalculation of the degree of interest.

Claims

1. A method for displaying hierarchically linked information, said hierarchically linked information comprised of a plurality of nodes each having one or more links to other of said plurality of nodes, said method comprising the steps of:

a) dynamically identifying a focus node for any of said plurality of nodes;

b) generating a degree of interest (DOI) value for each of said plurality of nodes, said degree of interest value relative to said focus node and sibling node order and corresponding to a node size; and

comprising the steps of;

b1) assigning a DOI value of 0 to the focus node and any parent node up to a root of the tree structure;

b2) assigning a DOI value of 0 to most interesting child node at user defined number of levels below focus node;

b3) assigning a DOI value of −

1 to siblings of nodes with value 0; and

b4) assigning a DOI value of one less than the parent node for all the rest of the nodes; and

c) laying out said plurality of nodes positioned based on associated links and sized based on associated degree of interest values in a tree structure;

d) identifying and performing any node compression necessary for boundedly displaying said hierarchically linked information based on the layout of said plurality of nodes; and

e) displaying said hierarchically linked information based on the layout of said plurality of nodes and node compression on a display area.

2. A method for displaying hierarchically linked information, said hierarchically linked information comprised of a plurality of nodes each having one or more links to other of said plurality of nodes, said method comprising the steps of:

a) dynamically identifying a focus node for any of said plurality of nodes;

b) generating a degree of interest (DOI) value for each of said plurality of nodes, said degree of interest value relative to said focus node and sibling order distance from the focus node order and corresponding to a node size; and

comprising the steps of;

b1) assigning a DOI value of −

1 to all selected nodes;

b2) assigning a DOI value of −

1 to the any parent node of selected nodes up to the root of the tree structure; and

b3) assigning a DOI value of one less than the parent node for all the rest of the nodes; and

c) laying out said plurality of nodes positioned based on associated links and sized based on associated degree of interest values in a tree structure;

d) identifying and performing any node compression necessary for boundedly displaying said hierarchically linked information based on the layout of said plurality of nodes; and

e) displaying said hierarchically linked information based on the layout of said plurality of nodes and node compression on a display area.

3. A method for displaying hierarchically linked information, said hierarchically linked information comprised of a plurality of nodes each having one or more links to other of said plurality of nodes, said method comprising the steps of:

a) dynamically identifying a focus node for any of said plurality of nodes;

b) generating a degree of interest (DOI) value for each of said plurality of nodes, said degree of interest value relative to said focus node and sibling order distance from the focus node order and corresponding to a node size;

c) laying out said plurality of nodes positioned based on associated links and sized based on associated degree of interest values in a tree structure;

d) identifying and performing any node compression necessary for boundingedly displaying said hierarchically linked information based on the layout of said plurality of nodes; and

e) displaying said hierarchically linked information based on the layout of said plurality of nodes and node compression on a display area;

allocating space for the focus node, parents of the focus node and siblings of the focus node in order to the right and left of the focus node until a first percentage of the horizontal partition of the display space remains; and

horizontally compressing the subtrees associated with a sibling node to fit below the sibling node.

4. A method for displaying hierarchically linked information, said hierarchically linked information comprised of a plurality of nodes each having one or more links to other of said plurality of nodes, said method comprising the steps of:

a) dynamically identifying a focus node for any of said plurality of nodes;

b) generating a degree of interest (DOI) value for each of said plurality of nodes, said degree of interest value relative to said focus node and sibling order distance from the focus node order and corresponding to a node size;

c) laying out said plurality of nodes positioned based on associated links and sized based on associated degree of interest values in a tree structure;

d) identifying and performing any node compression necessary for boundingedly displaying said hierarchically linked information based on the layout of said plurality of nodes; and

e) displaying said hierarchically linked information based on the layout of said plurality of nodes and node compression on a display area; and

wherein for large numbers of nodes to be displayed in a first direction of the display area;

determining a regular free layout zone, at least one compression zone and at least one aggregation zone in the first direction of the display area; and

allocating a large percentage of the display space to the regular free layout zone, a smaller percentage of the display area to the at least one compression zone and the smallest percentage to the at least one aggregation zone in the first direction.

5. The method of claim 4, further comprising the step of displaying proportionately representative and proportionately selectable display elements in the aggregation zone.