Method and apparatus for the viewing and exploration of the content of hierarchical information

• US 20040205536A1
• Filed: 09/10/2001
• Published: 10/14/2004
• Est. Priority Date: 09/10/2001
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Card, Stuart K., Newman, Paula S.
• Granted Patent: US 6,944,818 B2
• Time in Patent Office: Days
• US Class Current: 715/509
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

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 treetable 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

1. ) A computing system for generating display specifications 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 edges is a root node, a node with no outgoing edges is a leaf node and a path is a series of nodes starting from any node and at each point proceeding along a directed edge in that direction to another node, a subtree is a portion of the nodes starting at any node and including all the nodes on all possible paths therefrom, wherein each node has associated information, on a display, said computing system comprising:

a) input means for receiving user input, and

b) computing means responsive to said input means capable of generating display specifications for producing an image of the tree structured information when received by a display processor, the image comprising a two-dimensional row and column arrangement of cells having a display area, 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 from the root to a leaf 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,

iii) each column represents a path from the root to a leaf, and all such paths are represented

iv) each node associated cell contains at least one selection element, and

c) output means responsive to said computing means for sending the display specifications to a display processor.

2. ) The computing system of claim 1 further comprising a display responsive to said output means for displaying the image.

3. ) The computing system of claim 1 wherein the user input indicates a focus selection and the computing means further generates a display specification such that the cells within the focus selection are visually different from the rest of the cells.

4. ) The computing system of claim 3 wherein the focus selection is a column selection.

5. ) The computing system of claim 3 wherein the focus selection is a subtree selection.

6. ) The computing system of claim 3 wherein the visual difference comprises the columns within the focus selection being larger than the columns outside the focus selection.

7. ) The computing system of claim 3 wherein each cell has a color and the visual difference comprises the color of the cells within the focus selection being different from the color of the cells outside the focus selection.

8. ) The computing system of claim 1 wherein the user input indicates a column selection and the computing means further generates a display specification such that the cells within the column selection are visually different from the rest of the cells.

9. ) The computing system of claim 8 wherein the visual difference comprises the columns within the focus selection being larger than the columns outside the focus selection.

10. ) The computing system of claim 9 wherein the user input further indicates a cell selection and the computing means further generates a display specification such that the selected cell is visually different from both the column selection cells and the rest of the cells.

11. ) The computing system of claim 1 wherein the user input indicates a subtree selection and the computing means further generates a display specification such that the cells within the subtree selection are visually different from the rest of the cells.

12. ) The computing system of claim 11 wherein the user input further indicates a cell selection and the computing means further generates a display specification such that the selected cell is visually different from both the subtree selection cells and the rest of the cells.

13. ) The computing system of claim 1 wherein the user input indicates a cell selection and the computing means further generates a display specification such that the the selected cell is visually different from the rest of the cells.

14. ) The computing system of claim 1 wherein the user input indicates a column selection and the computing means further generates a display specification such that only those cells within the column selection will be displayed.

15. ) The computing system of claim 14 wherein the column selection indicates a portion of the columns.

16. ) The computing system of claim 14 wherein the column selection indicates all of the columns.

17. ) The computing system of claim 1 wherein the user input indicates a subtree selection and the computing means further generates a display specification such that only those cells within the subtree selection are displayed.

18. ) The computing system of claim 1 wherein the user input indicates a size selection and the computing means further generates a display specification such that the display area is changed.

19. ) The computing system of claim 18 wherein the display area is made larger.

20. ) The computing system of claim 18 wherein the display area is made smaller.

21. ) The computing system of claim 1 wherein the user input indicates a reading selection and the computing means further generates a display specification such that a reading view of the information associated with the nodes associated with the cells in the reading selection is displayed.

22. ) The computing system of claim 21 wherein the information is presented in a sequential, concatenated format.

23. ) The computing system of claim 21 wherein the information is reduced to essential content.

24. ) The computing system of claim 23 wherein the information is reduced to the essential content necessary for comprehension of the reading selection.

25. ) The computing system of claim 21 wherein the reading selection comprises a column selection.

26. ) The computing system of claim 21 wherein the reading selection comprises a selection of the nodes immediately succeeding a given node on all paths which include the given node.

27. ) The computing system of claim 21 wherein the reading selection comprises a selection of nodes consisting of a given node and all nodes immediately succeeding the given node on all paths which include the given node.

28. ) The computing system of claim 21 wherein the reading view is displayed in the same display area previously occupied by the image of the tree-structured information.

29. ) The computing system of claim 21 wherein the reading view is displayed in a different display area from the image of the tree-structured information.

30. ) The computing system of claim 21 wherein the reading view shares the display area with the tree structured information.

31. ) The computing system of claim 1 wherein at least one cell is populated with at least some of the information associated with the node associated with the cell.

32. ) A computing system for generating 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 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 no incoming edge, a leaf node is a node without any outgoing edges, a path is a series of nodes starting from one node, and at each point proceeding along a directed edge in that direction to another node until the end of the path is reached, wherein a full path is a path from a root node ending at a leaf node, 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, said computing system comprising:

A) input means for receiving user input, and

B) computing means responsive to said input means capable of generating display specifications for producing an image of the hierarchical information when received by a display processor, the image comprising;

i) 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, wherein

a) 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,

b) child cells of each cell are placed in a row n+1,

c) leaf cells span exactly one column,

d) cells other than leaf cells span exactly the columns spanned by the child cells associated with that cell, and

e) each cell contains a selection element, and

C) output means responsive to said computing means for sending the display specifications to a display processor.

33. ) A computing system for generating 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 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 series of nodes starting from one node, and at each point proceeding along a directed edge in that direction to another node until the end of the path is reached, wherein a full path is a path from a root node ending at a leaf node, in a display image having a plurality of rows, each row having a height, and a plurality of columns, each column having a width, said computing system comprising:

A) input means for receiving user input, and

B) computing means responsive to said input means capable of generating display specifications for producing an image of the hierarchical information when received by a display processor, the image comprising;

i) 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, wherein

a) each node has a span value where the span value is the number of leaf nodes that are on paths that include the node,

b) the root cell is located in the first row and spans all of the columns of the first row of the display image,

c) child cells are located in consecutive rows of the display image for each child node of each parent node in the previous row where each child node spans the number of columns equal to its span number and is placed to span at least a portion of the same columns spanned by its parent cell,

d) cells other than leaf cells span exactly the columns spanned by the child cells associated with that cell,

e) leaf cells span one column, and

f) each cell contains at least one selection element, and

C) output means responsive to said computing means for sending the display specifications to a display processor.