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

• US 7,392,488 B2
• Filed: 07/20/2005
• Issued: 06/24/2008
• 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: Nation, David A., Card, Stuart K.
• Primary Examiner(s): Wiley; David A.
• Assistant Examiner(s): Johnson; Grant D
• Application Number:
  US11/185,357
• Publication Number:
  US 20050273730A1
• Time in Patent Office: 1,070 Days
• Field of Search: 715/713, 715/853, 715/854, 715/855, 345/356, 707/101, 707/102
• 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 first focus node for any of said plurality of nodes;

b) generating a first degree of interest (DOI) value for each of said plurality of nodes, said degree of interest value relative to said first focus node and sibling order distance from the first focus node 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 first 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;

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

f) detecting that a user has selected a second focus node;

g) generating a second degree of interest value for each of said plurality of nodes relative to said second focus node;

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

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

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

2. The method as recited in claim 1 wherein said step of laying out said plurality of nodes positioned based on associated links and sized based on at least one of the first and second degree of interest values in at least one of the first and second tree structures is further comprised of the steps of:

c1) determining if said tree structure will fit vertically into said display area;

c2) if said layout does not fit into said display area, reducing node spacing and/or sizes proportionally until node-link tree structure fits in said display area.

3. The method as recited in claim 1 wherein said step of identifying and performing any node compression necessary for displaying said linked information based on the layout of said plurality of nodes is further comprised of the steps of:

d1) determining from said layout that said nodes will not fit horizontally into said display area; and

d2) causing nodes at the edges of the display area to be overlapped.

4. The method as recited in claim 1 wherein said step of identifying and performing any node compression necessary for displaying said linked information based on the layout of said plurality of nodes is further comprised of the steps of:

d1) determining from said layout that said nodes will not fit horizontally into said display area because certain levels are too wide; and

d2) causing sibling nodes at wide levels to be folded into multiple rows in the display area.

5. The method as recited in claim 1 wherein said step of identifying and performing any node compression necessary for displaying said linked information based on the layout of said plurality of nodes is further comprised of the steps of:

d1) determining from said layout that said nodes will not fit vertically into said display area;

d2) identifying subtrees in said layout causing said layout not to fit in said display area;

d3) causing said subtrees to be displayed in a manner proportionate to the size of the subtree.

6. The method as recited in claim 1 wherein prior to step e) or j) performing the steps of:

determining that there is unused display area for said structure;

identifying most interesting nodes for utilizing said unused display area; and

generating new first or second degree of interest values for said identified most interesting nodes and their linked decedent nodes.

7. The method as recited in claim 1 wherein said step of displaying said linked information is further comprised of the step of displaying a first or a second set of data items associated with said nodes.

8. The method as recited in claim 7 further comprising the step of:

detecting that a user has requested that a second set of data items associated with said nodes be displayed; and

displaying said second set of data items associated with said nodes.

9. The method as recited in claim 8 wherein said nodes are displayed to appear as three-dimensional objects having a plurality of display surfaces and said step of displaying said second set of data items associated with said nodes is comprised of the step of animating movement of said node to display a second surface of said node having said second set of data items.

10. The method of claim 1, in which generating at least one of the first or second degree of interest value comprises of the steps of:

determining a degree of interest based on distance to the focus node; and

determining a fractional degree of interest adjustment for the degree of interest based on the sibling order distance from the focus node.

11. The method of claim 10, in which determining the fractional degree of interest adjustment is based on at least one of:

reducing and increasing the fractional degree of interest adjustment.

12. The method of claim 11, in which the fractional degree of interest is less than 1.

13. The method of claim 10, in which degree of interest for child nodes of a sibling node are based on the degree of interest for the sibling node.

14. The method of claim 1, further comprising the steps of:

determining one or more sets of nodes from the plurality of linked nodes, the nodes in each set associated with a plurality of faces;

associating groups of display items to successive faces of the one or more sets of nodes from the plurality of linked nodes; and

rotating all of the nodes in each set simultaneously based on a user input.

15. The method of claim 14, in which display items in each group are related.

16. The method of claim 14, in which the user input is at least one of:

a gesture, a mouse input and a voice input.

17. The method of claim 14, in which the display is at least one of:

a two dimensional display and a three dimensional display.

18. The method of claim 1, further comprising the steps of:

associating each node with prioritized hierarchically linked information; and

selectively displaying hierarchically linked information for a node based on the node size and the priority of the hierarchically linked information.

19. The method of claim 1, further comprising the steps of:

associating each node with hierarchically linked information; and

selectively transforming the hierarchically linked information associated with a node based on the size of the node.

20. The method of claim 19, in which transforming the hierarchically linked information for a node is based on at least one of:

deleting less salient hierarchically linked information;

selectively abbreviating a portion of the hierarchically linked information.

21. System for browsing a collection of hierarchically linked data comprising:

display means having a display area for presenting views of a visualization of said collection of hierarchically linked data;

input device for providing input to change view of said visualization of said collection of linked data based on dynamically selected linked data;

visualization processing element coupled to said display means and said input device, said visualization processing element for creating a first bounded tree structure visualization of said collection of hierarchically linked data based on a First Degree of Interest relative to a first focus node and sibling order distance from the first focus node and a size of said display area;

detection element for detecting that a user has selected a second focus node; and

said visualization processing element for creating a second bounded tree structure visualization of said collection of hierarchically linked data based on a Second Degree of Interest relative to the second focus node and sibling order distance from the second focus node and the size of said display area.

22. The system as recited in claim 21 wherein said visualization processing element is further comprised of:

at least one of a first and second Degree of Interest (DOI) calculation element;

a node layout element; and

a node compression element.

23. The system as recited in claim 22 wherein said visualization processing element is further comprised of a node expansion element.

24. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps 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 first focus node for any of said plurality of nodes;

b) generating a first degree of interest (DOI) value for each of said plurality of nodes, said first degree of interest value relative to said first focus node and sibling order distance from the first focus node 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 first 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;

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

f) detecting that a user has selected a second focus node;

g) generating a second degree of interest value for each of said plurality of nodes relative to said second focus node;

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

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

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

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

dynamically identifying at least two focus nodes from any of said plurality of nodes;

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

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

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

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

detecting that a user has selected at least a third and forth focus node;

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

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

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

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