# US 2004/0205535 A1 · Method and apparatus for the construction and use of table-like visualizations of hierarchic material

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0205535 A1
- Document ID: US20040205535A1
- Status: Published application
- Kind: A1
- Application number: 09/954,388
- Filed: 2001-09-10
- Published: 2004-10-14
- Earliest claimed: 2001-09-10
- Assignees: Xerox Corporation
- Inventors: Paula S. Newman; Stuart K. Card
- Web page: https://patentgrep.com/patent/US20040205535A1

## CPC

- G06F 40/103: Formatting, i.e. changing of presentation of documents (automatic justification G06F40/189; automatic line break hyphenation G06F40/191)
- G06F 40/14: Tree-structured documents (parsing G06F40/205; validation G06F40/226)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for the conversion and display of tree-structured information to a “treetable”, a table-like display structure, in which each path from a root to a leaf node is represented by a single column, and cells representing the immediate successors of a node are placed immediately under that node. Variation in the amount of space given to cells within particular columns is used to allow more detail to be given for selected paths and subtrees. Extraction of subparts of a treetable into another such structure is used for deeper exploration of trees. The treatable structure is also suitable for use as a selector and guide to the reading, in auxiliary displays, of the concatenated node content associated with either (a) individual columns (representing full paths), or (b) all successors to a given node.

## Claims

### Claim 1

1) A method for displaying hierarchical information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information and the nodes are connected by directed edges wherein a node has at most one incoming edge, a parent node is the source of an incoming edge, a child node is the target of an outgoing edge, a root node is a node with no incoming edge, a leaf node is a node with no outgoing edges, a path is a sequence of nodes having a first node and a last node, and each node except the last node is followed by one of its child nodes, and a full path is a path n wherein the root node is the first node of the path and a leaf node is the last node of the path, in a two-dimensional structure having a plurality of rows, each row having a height, and a plurality of columns, each column having a width comprising:
a) generating a two-dimensional structure for containing cells associated with each node wherein the number of the plurality of rows equals the number of the nodes in the longest path, and the number of the plurality of columns equals the total number of the leaf nodes, and a cell associated with a parent node is a parent cell, a cell associated with a child node is a child cell, and a cell associated with a leaf node is a leaf cell,
b) designating a placement for each of the cells in a row n within the two-dimensional structure such that the parent cells of each cell are placed in a row n−1, child cells of each cell are placed in a row n+1, each leaf cell spans exactly one column, and each cell other than a leaf cell spans exactly the columns spanned by the child cells associated with that cell,
c) populating at least one cell with at least a portion of the information associated with the cell's associated node.

### Claim 2 (depends on 1)

2) The method of claim 1 further comprising displaying the two-dimensional structure on a display device.

### Claim 3 (depends on 1)

3) The method of claim 1 wherein the height of each row is substantially the same.

### Claim 4 (depends on 1)

4) The method of claim 1 wherein the width of each row is substantially the same.

### Claim 5 (depends on 1)

5) The method of claim 1 wherein at least one column may be designated as a focus column and the width of the focus columns are larger than the width of the non-focus columns.

### Claim 6 (depends on 1)

6) The method of claim 1 wherein at last one column may be designated as a focus column and the cells spanning the focus columns are visually differentiated from the cells not spanning the focus columns.

### Claim 7 (depends on 1)

7) The method of claim 1 wherein a portion of the two-dimensional structure may be designated as a focus portion and the cells contained in the focus portion are larger than the cells not contained in the focus portion.

### Claim 8 (depends on 1)

8) The method of claim 1 wherein a portion of the two-dimensional structure may be designated as a focus portion and the cells contained in the focus portion are visually differentiated from the cells not contained in the focus portion.

### Claim 9 (depends on 8)

9) The method of claim 8 wherein a cell within the focus portion may be designated as a focus cell and the focus cell is visually differentiated from the other cells in the focus portion.

### Claim 10

10) A computer controlled display system for displaying tree-structured information having a multiplicity of nodes connected by directed edges wherein any node has at most one incoming edge, a node with no incoming edge is a root node, a node with no outgoing edges is a leaf node a path is a series of nodes having a first node and a last node obtained by starting at the first node and proceeding along the directed edges in the direction of the edges to the last node, and a full path is a path wherein the root node is the first node of the path and a leaf node is the last node of the path, wherein each node has associated information, in a table on a display, said computer controlled display system comprising:
a) computing means responsive to said input means for generating display specifications for displaying said table and said tree structured information, said table comprising a two-dimensional row and column arrangement of cells wherein each node is associated with a cell, said arrangement having a number of rows equal to the number of nodes in the longest path and a number of columns equal to the number of leaf nodes wherein:
i) a root node associated cell is placed in a first row,
ii) node associated cells along a path are placed in series in consecutive rows from the first row wherein each node associated cell spans the greater of one column or the number of columns equal to the number of leaf nodes which are located on paths from the node associated with the node associated cell, and each column represents a path, and
iii) at least one node associated cell contains at least part of the information associated with the node, and
b) display processing means responsive to said computing means for receiving the display specifications and displaying the table.

### Claim 11

11) A memory medium comprising software programmed to generate display specifications for displaying hierarchical information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information and the nodes are connected by directed edges wherein a parent node is the source of an incoming edge, a child node is the target of an outgoing edge and a path is a sequence of nodes progressing from parent node to child node, wherein a root node is the first node of the path and a leaf node is the last node of the path, in a two-dimensional structure having a plurality of rows, each row having a height, and a plurality of columns, each column having a width by:
a) generating a two-dimensional structure for containing cells associated with each node wherein the number of the plurality of rows equals the number of the nodes in the longest path, and the number of the plurality of columns equals the total number of the leaf nodes, and a cell associated with a parent node is a parent cell, a cell associated with a child node is a child cell, and a cell associated with a leaf node is a leaf cell,
b) designating a placement for each of the cells in a row n within the two-dimensional structure such that the parent cells of each cell are placed in a row n−1, child cells of each cell are placed in a row n+1, each leaf cell spans exactly one column, and each cell other than a leaf cell spans at least the columns spanned by the child cells associated with that cell,
c) populating at least one cell with at least a portion of the information associated with the cell's associated node.

### Claim 13

13) A computer programmed to execute a process for displaying hierarchical information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information and the nodes are connected by directed edges wherein a parent node is the source of an incoming edge, a child node is the target of an outgoing edge and a path is a sequence of nodes progressing from parent node to child node wherein a root node is the first node of the path and a leaf node is the last node of the path, in a two-dimensional structure having a plurality of rows, each row having a height, and a plurality of columns, each column having a width, the process comprising:
a) generating a two-dimensional structure for containing cells associated with each node wherein the number of the plurality of rows equals the number of the nodes in the longest path, and the number of the plurality of columns equals the total number of the leaf nodes, and a cell associated with a parent node is a parent cell, a cell associated with a child node is a child cell, and a cell associated with a leaf node is a leaf cell,
b) designating a placement for each of the cells in a row n within the two-dimensional structure such that the parent cells of each cell are placed in a row n−1, child cells of each cell are placed in a row n+1, each leaf cell spans exactly one column, and each cell other than a leaf cell spans at least the columns spanned by the child cells associated with that cell,
c) populating at least one cell with at least a portion of the information associated with the cell's associated node.

### Claim 14

14) A computer controlled display system for displaying hierarchically related information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information and the nodes are connected by directed edges wherein a each node has at most one incoming edge, a parent node is the source of an incoming edge, a child node is the target of an outgoing edge, a root node is a node with no incoming edges, a leaf node is a node with no outgoing edges, a path is a sequence of nodes having a first node and a last node, and each node except the last node is followed by one of its child nodes, and a full path is a path wherein the root node is the first node of the path and a leaf node is the last node of the path, in a two-dimensional structure having a plurality of rows, each row having a height, and a plurality of columns, each column having a width comprising:
a) a processor for generating display specifications from the hierarchically related information, and a
b) a display responsive to the processor wherein the hierarchically related information is displayed as a two-dimensional structure containing cells associated with each node wherein the number of the plurality of rows equals the number of the nodes in the longest path, and the number of the plurality of columns equals the total number of the leaf nodes, and a cell associated with a parent node is a parent cell, a cell associated with a child node is a child cell, and a cell associated with a leaf node is a leaf cell, each of the cells is placed in a row n within the two-dimensional structure such that the parent cells of each cell are placed in a row n−1, child cells of each cell are placed in a row n+1, each leaf cell spans exactly one column, and each cell other than a leaf cell spans exactly the columns spanned by the child cells associated with that cell, and at least one cell displays at least a portion of the information associated with the cell's associated node.

### Claim 15

15) A computer controlled display system for displaying hierarchically related information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information and the nodes are connected by directed edges wherein each node has at most one incoming edge, a root node is a node with no incoming edge, a leaf node is a node with no outgoing edges, a parent node is the source of an incoming edge, a child node is the target of an outgoing edge and a path is a sequence of nodes starting at a first node and ending at a last node so that each node except the last is followed by one of its child nodes, and a full path is a path wherein the root node is the first node of the path and a leaf node is the last node of the path, in a two-dimensional structure having a plurality of rows, each row having a height, and a plurality of columns, each column having a width comprising:
a) a processing element for generating a display specification, and a
b) a display element wherein the display specification is displayed as a two-dimensional structure containing cells associated with each node wherein the number of the plurality of rows equals the number of the nodes in the longest path, and the number of the plurality of columns equals the total number of the leaf nodes, and a cell associated with a parent node is a parent cell, a cell associated with a child node is a child cell, and a cell associated with a leaf node is a leaf cell, each of the cells is placed in a row n within the two-dimensional structure such that the parent cells of each cell are placed in a row n−1, child cells of each cell are placed in a row n+1, each leaf cell spans exactly one column, and each cell other than a leaf cell spans exactly the columns spanned by the child cells associated with that cell, and at least one cell displays at least a portion of the information associated with the cell's associated node.

### Claim 16

16) A method for displaying hierarchically related information, where the information can be represented as a set of nodes wherein each node is associated with a portion of the information and the nodes are connected by directed edges wherein each node has at most one incoming edge, a parent node is the source of an incoming edge, a child node is the target of an outgoing edge, a root node is a node with no incoming edge, a leaf node is a node with no outgoing edges, and a path is a sequence of nodes having a first node and a last node, and each node except the last node is followed by one of its child nodes, and a full path is a path wherein the root node is the first node of the path and a leaf node is the last node of the path, in a display image having a plurality of rows, each row having a height, and a plurality of columns, each column having a width, the method comprising:
a) generating a display image containing cells associated with each node wherein the number of the plurality of rows equals the number of the nodes in the longest path, and the number of the plurality of columns equals the total number of the leaf nodes, a cell associated with a parent node is a parent cell, a cell associated with a child node is a child cell, a cell associated with a leaf node is a leaf cell, and a cell associated with a leaf node is a leaf cell,
b) determining a span value for each node where the span value is the number of leaf nodes that are on paths that include the node,
c) allocating a root cell which spans all of the columns of the first row of the display image,
d) allocating a child cell in the consecutive row of the display image for each child node of each parent node in the previous row where each child cell spans the number of columns equal to the span number of its associated child node and is placed to span at least a portion of the same columns spanned by its parent cell, and all child cells of a particular parent cell in the previous row together span the columns spanned by the parent cell, and
e) populating at least one cell with at least a portion of the information associated with the cell's associated node.
