Usage based methods of traversing and displaying generalized graph structures

• US 6,509,898 B2
• Filed: 04/17/1998
• Issued: 01/21/2003
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chi, Ed H., Pirolli, Peter L. T., Pitkow, James E., Card, Stuart K., Mackinlay, Jock D., Gossweller, Rich
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US09/062,341
• Publication Number:
  US 20020067360A1
• Time in Patent Office: 1,740 Days
• Field of Search: 345/440, 345/357, 345/356, 345/335, 345/342, 345/346, 345/459, 345/327, 345/729, 345/738, 345/853, 707/3
• US Class Current: 345/440
• CPC Class Codes: G06F 16/748 Hypervideo linking data to content, e.g. by linking an URL to a video object in the context of video distribution systems H04N21/858
• CPC Class Codes: G06F 16/94 Hypermedia Hyperlinking G06F40/134
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method for generating a tree structure representation of a generalized graph structure for display includes the more important links in the representation. Usage parameters are referenced in generating the tree structure from the generalized graph structure. Frequency, recency, spacing of accesses, and path information are exemplary types of usage parameters. A breadth-first or depth-first traversal of the graph references usage parameters associated with each node or link. The usage parameters which are associated with each node are referenced in order to determine the visitation order. The visitation order is determined by visiting the highest used nodes or links first. A method of displaying the tree structure references the usage parameters to determine the positioning of the nodes in the layout of the tree structure. In a preferred embodiment, the root node is positioned in the center of the layout. In one example, sibling nodes are spread out on links which emanate radially about their parent. The highest-used sibling nodes can be placed farthest apart from each other so as to achieve optimal separation so that they have the most growth space. The lowest-used nodes are then placed in the remaining space between the high-usage nodes. In another example, sibling nodes are positioned at the same radius from the root node. Each leaf node in the hierarchy is assigned the same amount of angular space. The layout angle of each node is a function of the ranking of the node'"'"'s usage parameter relative to its siblings. Derived usage parameters such as need probability, cocitation clustering, or functions of both node and link usages can alternatively be referenced.

Claims

1. A method for generating a tree structure from a generalized graph structure, the method comprising the steps of:

(a) selecting a first node within the generalized graph structure;

(b) displaying the first node;

(c) identifying a first child node of the first node having a first child usage parameter value and a second child node of the first node having a second child usage parameter value; and

,

(d) displaying the first child node and the second child node responsive to a comparison of the first child usage parameter value and the second child usage parameter value.

2. A method as in claim 1, further comprising:

(e) selecting a second node within the generalized graph structure at a current depth from a root node, wherein the first node has a first node usage parameter value and the second node has a second node usage parameter value.

3. A method as in claim 2, further comprising the step of:

(f) displaying the second node responsive to a comparison of the first node usage parameter value and the second node usage parameter value.

4. A method as in claim 3, further comprising the step of:

(g) incrementing the current depth if all nodes at the current depth have been selected.

5. A method as in claim 1, wherein the first node is a root node.

6. A method as in claim 1,

wherein the first child usage parameter value is a measure of usage of that node.

7. A method as in claim 1,

wherein the first child usage parameter value is a measure of usage of a link from its parent node to itself.

8. A method for displaying a tree structure, the method comprising the steps of:

(a) for each group of sibling nodes in the tree structure, ranking the sibling nodes according to a usage parameter value associated with each node; and

(b) positioning each group of sibling nodes in accordance with the rankings of the sibling nodes.

9. A method as in claim 8, wherein step (b) comprises the step of:

(c) laying out the tree structure such that a root node is placed in a center of a layout of the tree structure and each child node in the tree structure is placed radially outward at a layout angle which is a function of its ranking.

10. A method as in claim 9,

wherein the layout angle for each child node is measured from the center of the layout of the tree structure.

11. A method as in claim 9,

wherein the layout angle for each child node is measured from its parent.

12. A method as in claim 10,

wherein the layout angles associated with sibling nodes increase monotonically with the rankings of the sibling nodes.

13. A method as in claim 11,

wherein the layout angles associated with sibling nodes are determined such that highest ranking sibling nodes are optimally separated.

14. A method as in claim 12,

wherein all nodes of the tree structure at a given radius from the center are at an equal depth in the tree structure.

15. A method as in claim 8, wherein each nodes'"'"'s usage parameter value is a measure of usage of that node.

16. A method as in claim 8, wherein each node'"'"'s usage parameter value is a measure of usage of a link from its parent node to itself.

17. A computer readable storage medium comprising:

computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for generating a tree structure from a generalized graph structure, the method comprising the steps of;

(a) selecting a first node within the generalized graph structure;

(b) displaying the first node;

(c) identifying a first child node of the first node having a first child usage parameter value and a second child node of the first node having a second child usage parameter value; and

,

(d) displaying the first child node and the second child node responsive to a comparison of the first child usage parameter value and the second child usage parameter value.

18. A computer readable storage medium comprising computer readable program code as in claim 17, further comprising:

(e) selecting a second node within the generalized graph structure at a current depth from a root node, wherein the first node has a first node usage parameter value and the second node has a second node usage parameter value.

19. A computer readable storage medium comprising computer readable program code as in claim 18, further comprising the step of:

(f) displaying the second node responsive to a comparison of the first node usage parameter value and the second node usage parameter value.

20. A computer readable storage medium comprising computer readable program code as in claim 19, further comprising the step of:

(g) incrementing the current depth if all nodes at the current depth have been selected.

21. A computer readable storage medium comprising computer readable program code as in claim 18, wherein the first node is a root node.

22. A computer readable storage medium comprising computer readable program code as in claim 18,

wherein the first child usage parameter value is a measure of usage of that node.

23. A computer readable storage medium comprising computer readable program code as in claim 18,

wherein the first child usage parameter value is a measure of usage of a link from its parent node to itself.

24. A computer readable storage medium comprising:

computer readable program code for programming a computer to perform a method for displaying a tree structure, the method comprising the steps of;

(a) for each group of sibling nodes in the tree structure, ranking the sibling nodes according to a usage parameter value associated with each node; and

(b) positioning each group of sibling nodes in accordance with the rankings of the sibling nodes.

25. A computer readable storage medium comprising computer readable program code as in claim 24, wherein step (b) comprises the step of:

(c) laying out the tree structure such that a root node is placed in a center of a layout of the tree structure and each child node in the tree structure is placed radially outward at a layout angle which is a function of its ranking.

26. A computer readable storage medium comprising computer readable program code as in claim 25,

wherein the layout angle for each child node is measured from the center of the layout of the tree structure.

27. A computer readable storage medium comprising computer readable program code as in claim 25,

wherein the layout angle for each child node is measured from its parent.

28. A computer readable storage medium comprising computer readable program code as in claim 26,

wherein the layout angles associated with sibling nodes increase monotonically with the rankings of the sibling nodes.

29. A computer readable storage medium comprising computer readable program code as in claim 27,

wherein the layout angles associated with sibling nodes are determined such that highest ranking sibling nodes are optimally separated.

30. A computer readable storage medium comprising computer readable program code as in claim 28,

wherein all nodes of the tree structure at a given radius from the center are at an equal depth in the tree structure.

31. A computer readable storage medium comprising computer readable program code as in claim 24, wherein each nodes'"'"'s usage parameter value is a measure of usage of that node.

32. A computer readable storage medium comprising computer readable program code as in claim 24, wherein each node'"'"'s usage parameter value is a measure of usage of a link from its parent node to itself.

33. An apparatus for generating a tree structure from a generalized graph structure, comprising:

a processor; and

a processor readable storage medium coupled to the processor containing processor readable program code for programming the apparatus to perform a method for generating the tree structure from the generalized graph structure, the method comprising the steps of;

(a) selecting a first node within the generalized graph structure;

(b) displaying the first node;

(c) identifying a first child node of the first node having a first child usage parameter value and a second child node of the first node having a second child usage parameter value; and

,

(d) displaying the first child node and the second child node responsive to a comparison of the first child usage parameter value and the second child usage parameter value.

34. An apparatus for displaying a tree structure, comprising:

a processor;

a display device coupled to the processor; and

a processor readable storage medium coupled to the processor containing processor readable program code for programming the apparatus to perform a method for displaying the tree structure, the method comprising the steps of;

(a) for each group of sibling nodes in the tree structure, ranking the sibling nodes according to a usage parameter value associated with each node; and

(b) positioning each group of sibling nodes in accordance with the rankings of the sibling nodes.