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

• US 20050273730A1
• Filed: 07/20/2005
• Published: 12/08/2005
• Est. Priority Date: 12/21/2000
• Status: Active Grant

• Current Assignee: Nation David, Stuart Card
• Original Assignee: Nation David, Stuart Card
• Inventors: Card, Stuart, Nation, David
• Granted Patent: US 7,392,488 B2
• Time in Patent Office: Days
• 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 order distance from the 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 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. The method as recited in claim 1 further comprising the step of:

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) repeating steps c)-e) using said second degree of interest value for each of said plurality of nodes.

3. 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 associated degree of interest values in a tree structure is further comprised of the steps of

c1) determining if said 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 structure fits in said, display area.

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; and

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

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

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

7. The method as recited in claim 1 wherein prior to step e) 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 degree of interest values for said identified most interesting nodes and their linked decedent nodes.

8. 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 set of data items associated with said nodes.

9. The method as recited in claim 8 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.

10. The method as recited in claim 9 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.

15. The method of claim 1, in which generating a 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.

16. The method of claim 15, 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.

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

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

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

20. The method of claim 19, in which display items in each group are related.

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

a gesture, a mouse input and a voice input.

22. The method of claim 19, in which the display is at least one of:

a two dimensional display and a three dimensional display.

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

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

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

deleting less salient hierarchically linked information;

selectively abbreviating a portion of the hierarchically linked information.

11. 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; and

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

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

a Degree of Interest (DOI) calculation element;

a node layout element; and

a node compression element.

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

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

26. 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 degree of interest (DOI) value for each of said plurality of nodes, said degree of interest value relative to the at least two focus nodes and to the sibling order distance from the at least 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 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 a display area.