Patent US6509898B2 successfully refreshed from Google Patents.
US6509898B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Usage based methods of traversing and displaying generalized graph structures
Assignee: Google LLC
•
Filing: 1998-04-17
•
Granted: 2003-01-21
•
Expires: 2018-04-17
Abstract
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.
Inventors
- 👤 Ed H. Chi
- 👤 Peter L. T. Pirolli
- 👤 James E. Pitkow
- 👤 Rich Gossweller
- 👤 Jock D. Mackinlay
- 👤 Stuart K. Card
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 13:40
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/955; G06F16/9558; G06F16/70; G06F16/74; G06F16/748; G06F16/93; G06F16/94; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
96 words
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.
Claim 2
Independent Claim
96 words
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.
Claim 3
Dependent Claim
49 words
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.
Claim 4
Dependent Claim
35 words
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.
Claim 5
Dependent Claim
27 words
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.
Claim 6
Dependent Claim
15 words
A method as in claim 1 , wherein the first node is a root node.
Claim 7
Dependent Claim
22 words
A method as in claim 1 , wherein the first child usage parameter value is a measure of usage of that node.
Claim 8
Dependent Claim
28 words
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.
Claim 9
Independent Claim
55 words
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.
Claim 10
Independent Claim
55 words
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.
Claim 11
Dependent Claim
60 words
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.
Claim 12
Dependent Claim
27 words
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.
Claim 13
Dependent Claim
20 words
A method as in claim 9 , wherein the layout angle for each child node is measured from its parent.
Claim 14
Dependent Claim
24 words
A method as in claim 10 , wherein the layout angles associated with sibling nodes increase monotonically with the rankings of the sibling nodes.
Claim 15
Dependent Claim
26 words
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.
Claim 16
Dependent Claim
30 words
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.
Claim 17
Dependent Claim
21 words
A method as in claim 8 , wherein each nodes's usage parameter value is a measure of usage of that node.
Claim 18
Dependent Claim
27 words
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.
Claim 19
Dependent Claim
124 words
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.
Claim 20
Dependent Claim
124 words
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.
Claim 21
Dependent Claim
57 words
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.
Claim 22
Dependent Claim
43 words
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.
Claim 23
Dependent Claim
35 words
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.
Claim 24
Dependent Claim
23 words
A computer readable storage medium comprising computer readable program code as in claim 18 , wherein the first node is a root node.
Claim 25
Dependent Claim
30 words
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.
Claim 26
Dependent Claim
36 words
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.
Claim 27
Dependent Claim
71 words
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.
Claim 28
Dependent Claim
71 words
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.
Claim 29
Dependent Claim
68 words
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.
Claim 30
Dependent Claim
35 words
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.
Claim 31
Dependent Claim
28 words
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.
Claim 32
Dependent Claim
32 words
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.
Claim 33
Dependent Claim
34 words
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.
Claim 34
Dependent Claim
38 words
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.
Claim 35
Dependent Claim
29 words
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.
Claim 36
Dependent Claim
35 words
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.
Claim 37
Independent Claim
132 words
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.
Claim 38
Independent Claim
132 words
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.
Claim 39
Independent Claim
93 words
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.
Claim 40
Independent Claim
93 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-01-20 | 2006-07-22 | 2007-01-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-01-20 | 2010-07-22 | 2011-01-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-01-20 | 2014-07-22 | 2015-01-21 | $7700.00 | Window Closed / Lapsed |