System and method for redistributing interest in a hierarchical data structure representation

CROSS-REFERENCE TO RELATED APPLICATIONS

p-0002This patent application is a continuation of U.S. patent application Ser. No. 11/401,026, filed Apr. 10, 2006, now U.S. Pat. No. 7,627,599, issued on Dec. 1, 2009, which claims priority from U.S. Provisional Patent Application Ser. No. 60/682,888, filed May 20, 2005, expired, the priority filing dates of which are claimed, and the disclosures of which are incorporated by reference.

INCORPORATION BY REFERENCE

p-0003The U.S. Government has a paid-up license in this invention and the right in limited circumstances to require the patent owner to license others on reasonable terms as provided for by the terms of MDA9O4-03-C-0404 awarded by ARDA.

FIELD

p-0004This technology disclosed herein relates to the field of visualizing hierarchical data structures, and in particular, to a system and method for redistributing interest in a hierarchical data structure representation.

BACKGROUND

p-0005There are many prior-art techniques for the visualization of hierarchical data structures (tree structures) that interconnect nodes. Examples of hierarchical data structures include file systems, organization charts, and taxonomies. In addition, many other richer graph structures, such as web sites, family trees, and social networks, are amenable to hierarchical data structure-based visualizations. Exponential increases in processing power, networking, and immense data storage have given rise to increasingly massive data sets and the need to visualize this. Information.

p-0006There is a problem with massive data sets being presented on limited display areas when the breadth or depth of a visualization of a hierarchical data structure exceeds the bounds of the display area. Common approaches to this problem use scrolling, panning, and/or scaling techniques. In addition, some techniques allow the visualization of the nodes to overlap (for example, most cone-tree embodiments).

p-0007A “Degree-Of-Interest” Tree (DOITree) can be represented as a hierarchical data structure where the nodes contain (or are associated with) an interest value (such as a degree-of-interest) and a payload. The layout of the DOITree structure and the payload depends on an interest value associated with each node in the tree. Some versions of DOITrees are interactive trees with animated transitions that fit within a bounded region of space and whose layout depends dynamically on the user's estimated degree-of-interest. DOITrees can use focus+context techniques to achieve the goals of logical filtering of nodes, using the estimated degree-of-interest to determine which nodes to display; geometric distortion, changing node sizes to match the estimated interest; semantic zooming of content based on node size; and aggregate representations of elided subtrees.

p-0008Similar in spirit to DOITrees is Plaisant et al.'s SpaceTree, which uses logical filtering and aggregation of nodes, combined with animation and automated camera management, to visualize tree structures. SpaceTree supports multiple foci, search, and filtering. However, for large hierarchical data structures SpaceTree usage often requires significant manual panning.

p-0009The visualization of massive data sets using exiting algorithms is computationally expensive. It would be advantageous to provide an improved, computationally efficient, visualization of hierarchical data structures that allows multiple foci and that can be presented within a constrained display area.

SUMMARY

p-0010An embodiment provides a system and method for redistributing interest in a hierarchical data structure representation. A data representation of a hierarchical data structure is displayed. The hierarchical data structure includes depth levels having one or more blocks of sibling nodes associated with node interest characteristics. Two or more of the sibling nodes are combined as aggregates into elided subsets. One of the elided subsets in one of the blocks is selected and expanded to reveal the aggregated sibling nodes. A breadth of the depth level is which the one block is located is determined. A determination that the breadth exceeds a constrained breadth extent for the data representation is made. The breadth is decreased by ordering the sibling nodes in the depth level by their respective node interest characteristic and by combining at least a portion of the sibling nodes in the depth level into the elided subset based on a comparison of the respective node interest characteristics such that the breadth does not exceed the constrained breadth extent.

p-0011Still other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is described embodiments of the invention by way of illustrating the best mode contemplated for carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the spirit and the scope of the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.

BRIEF DESCRIPTION OF THE DRAWINGS

p-0012The embodiments of the invention will be described in detail, with reference to the following figures wherein:

p-0013<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a networked computer system that can utilize the disclosed technology;

p-0014<figref idrefs="DRAWINGS">FIG. 2</figref> illustrates one embodiment of a ‘depth level’ data structure;

p-0015<figref idrefs="DRAWINGS">FIG. 3</figref> illustrates one embodiment of a ‘space list’ entry;

p-0016<figref idrefs="DRAWINGS">FIG. 4</figref> illustrates one embodiment of a layout process;

p-0017<figref idrefs="DRAWINGS">FIG. 5</figref> illustrates one embodiment of a ‘construct block representation of the hierarchical data structure’ process that can be invoked by the layout process of <figref idrefs="DRAWINGS">FIG. 4</figref>;

p-0018<figref idrefs="DRAWINGS">FIG. 6</figref> illustrates one embodiment of a ‘recursive extent’ function that can be invoked by the ‘construct block representation of the hierarchical data structure’ process of <figref idrefs="DRAWINGS">FIG. 5</figref>;

p-0019<figref idrefs="DRAWINGS">FIG. 7</figref> illustrates one embodiment of an ‘aggregate nodes’ process that can be invoked by <figref idrefs="DRAWINGS">FIG. 4</figref>;

p-0020<figref idrefs="DRAWINGS">FIG. 8</figref> illustrates one embodiment of an ‘allocate breadth’ process that can be invoked by the layout process of <figref idrefs="DRAWINGS">FIG. 4</figref>;

p-0021<figref idrefs="DRAWINGS">FIG. 9</figref> illustrates a presentation process that can be invoked by <figref idrefs="DRAWINGS">FIG. 4</figref>; and

p-0022<figref idrefs="DRAWINGS">FIG. 10</figref> illustrates an example visualization image of a hierarchical data structure showing features resulting from the disclosed technology.

DETAILED DESCRIPTION

p-0023One aspect of the technology disclosed herein for a computationally efficient layout of a hierarchical data structure includes a method of receiving the hierarchical data structure that contains information that can be presented within a constrained display area. The constrained display area having a constrained depth extent and a constrained breadth extent. The hierarchical data structure including nodes that have a respective node interest characteristic. Once the hierarchical data structure is received, it is used to construct a block representation represented by block descriptors, that are associated with depth levels, each which have a depth level breadth extent. Once the block representation is constructed, it is used to determine whether the respective depth level breadth extent for one of the depth levels exceeds the constrained breadth extent. This depth level is associated with at least one of the block descriptors that is, in turn, associated with a first subset of the nodes. The respective depth level breadth extent is responsive to the extents of the first subset of the nodes. Once the extent of a depth level is determined to be too large, the nodes in the depth level are sorted by the respective node interest characteristic and partitioned into an elided subset and a visualized subset, the depth level breadth extent being reduced by the extents of the elided subset to not exceed the constrained breadth extent. Once the depth level extent is reduced such that the visualized subset of the nodes making up the depth level can fit within the constrained display area, the nodes in the visualized subset are positioned and their information presented within the constrained display area.

p-0024The following ‘notations and nomenclature’ are provided to assist in the understanding of the disclosed technology and the embodiments thereof.

p-0025Data Structure—A data structure is an ordered arrangement of storage for variables. A data structure can be as simple as a small integer, or as complex as a relational database.

p-0026Pointer—A pointer is a data value that is used to reference a data structure or an object. One skilled in the art will understand that “pointer” includes, without limitation, a memory address to, or a value used to calculate the address to the information of interest and any functional equivalents including handles, hashes and/or similar constructs as well as database or registry keys and their equivalents.

p-0027Procedure—A procedure is a self-consistent sequence of steps that can be performed by a programmed computer, specialized electronics or other circuitry or a combination thereof that lead to a desired result. These steps can be defined by one or more computer instructions. These steps can be performed by a computer executing the instructions that define the steps. Thus, the term “procedure” can refer (for example, but without limitation) to a sequence of instructions, a sequence of instructions organized within a programmed-procedure or programmed-function, a sequence of instructions organized within programmed-processes executing in one or more computers, or a sequence of steps performed by electronic or other logic circuitry.

p-0028<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a networked computer system <b>100</b> that can incorporate an embodiment of the technology herein disclosed. The networked computer system <b>100</b> includes a computer <b>101</b> that incorporates a CPU <b>103</b>, a memory <b>105</b>, and a network interface <b>107</b>. The network interface <b>107</b> provides the computer <b>101</b> with access to a network <b>109</b>. The computer <b>101</b> also-includes an I/O interface <b>111</b> that can be connected to a user interface device(s) <b>113</b>, a storage system <b>115</b>, and a removable data device <b>117</b>. The removable data device <b>117</b> can read a computer-usable data carrier <b>119</b> (such as a ROM within the device, within replaceable ROM, in a computer-usable data carrier such as a memory stick, CD, floppy, DVD or any other tangible media) that typically contains or provides a program product <b>121</b>. The user interface device(s) <b>113</b> can include a display device <b>125</b>. The storage system <b>115</b> (along with the removable data device <b>117</b>), the computer-usable data carrier <b>119</b>, and (in some-cases the network <b>109</b>) comprise a file storage mechanism. The program product <b>121</b> on the computer-usable data carrier <b>119</b> is generally read into the memory <b>105</b> as a program <b>123</b>, which instructs the CPU <b>103</b> to perform specified operations. In addition, the program product <b>121</b> can be provided from devices accessed using the network <b>109</b>. One skilled in the art will understand that the network transmits information (such as data that defines a computer program). Generally, the information is embodied within a carrier-wave. The term “carrier-wave” includes electromagnetic signals, visible or invisible light pulses, signals on a data bus, or signals transmitted over any wire, wireless, or optical fiber technology that allows information to be transmitted from one point to another. Programs and data are commonly provided by reading the data read from both tangible physical media (such as those listed above) and from the network <b>109</b>. Thus the network <b>109</b>, like a tangible physical media, is a computer-usable data carrier. One skilled in the art will understand that not all of the displayed features of the computer <b>101</b> need to be present use the claimed technology. In particular, the network <b>109</b> is not needed if the program <b>123</b> is accessed from the removable data device <b>117</b> or the storage system <b>115</b>.

p-0029The hierarchical data structure layout technology described herein was initially developed to improve the computational efficiency of, the visualization of, and the user interaction with DOITrees. However, the layout technology can be applied to any hierarchical data structure that includes information that can be presented or visualized. This information is often textual in nature. The DOITree can be presented (displayed) as a visualization. The user can select one or more nodes on the visualization and designate them as focus-nodes (for example, to support comparison across tree branches). Some DOITree browsers can also designate search terms as focus-nodes. Other focus-nodes can be pegged nodes, that is, nodes that a user desires to always be displayed. As the user has provided input into his/her interest, the underlying focus+context engine can redistribute the estimated interest between the nodes and provide a set of possibly visualized nodes within a hierarchical data structure for visualization using the technology disclosed herein. In addition, some embodiments will initiate a smooth, slow-in slow-out animation between tree configurations. For example, newly visible nodes can flow out from their parents, while other previously visible nodes become hidden, returning to their parents and fading out to transparency, ultimately being replaced by an elision graphic indicating the size of the unexpanded subtree. In one embodiment, newly visible nodes are initially highlighted to help users track the appearance of previously unseen information.

p-0030One embodiment of the underlying focus+context engine is disclosed by U.S. Pat. No. 6,944,830, issued Sep. 13, 2005, and hereby incorporated by reference. The underlying DOITree technology provides a hierarchical data structure for visualization to the subsequently described layout technology. One skilled in the art will understand that any hierarchical data structure having nodes that contains or reference a respective node interest characteristic, no matter how constructed can use this layout technology and that the layout technology can be used for visualization of data sets other than that sourced by DOITrees.

p-0031The layout technology disclosed herein presents a visualization of the supplied hierarchical data structure by expanding multiple tree branches responsive to the focus-node(s), and maximizing the allocated space for each expanded branch within the constrained breadth extent of the constrained display area of the display. Deeper tree paths expand to use up available space underneath other, shorter tree paths. When the breadth of the expanded tree branches exceeds the constrained breadth extent, the nodes of lowest estimated interest are automatically culled until the branch fits within the constrained display area. In some embodiments these culled nodes (elided nodes) can be indicated with an aggregate representation as is shown in <figref idrefs="DRAWINGS">FIG. 10</figref>. In these embodiments, if the user then selects the aggregate, the underlying focus+context engine can redistribute the interest between the nodes in the branch and provide an updated hierarchical data structure for visualization. This expands the aggregate, revealing hidden nodes, while aggregating previously visible nodes.

p-0032As increasingly deeper levels of the tree are visualized, the depth of the supplied hierarchical data structure may exceed-the constrained depth extent of the constrained display area of the display. As was previously described, scrolling/panning and scaling techniques can be applied. In one embodiment, the visualization technology provides automatic panning of the hierarchical data structure visualization responsive to the most recent user-selected focus-node. To provide tree context, the visualization technology maintains tree context by presenting an “elided depth level trail” of ancestor nodes along the periphery of the visualization (see <figref idrefs="DRAWINGS">FIG. 10</figref>). A user can designate one of the ancestor nodes in the elided depth level trail node to be a focus-node with the expected redistribution of interest and resulting visualization update. Other nodes can be designated as pegged nodes. Pegged nodes are focus-nodes that the user desires to always have visualized, and need not be in the branch of the user's most recently selected focus-node.

p-0033In some embodiments, (for example, an information browser) nodes that match a query can be highlighted (and/or designated as focus-nodes that causes all filtered branches containing search hits to be expanded) in the visualization. Furthermore, subtree aggregates can be highlighted to indicate branches containing search hits. A linear list of search results can be made available to the user; and activation of an entry in the results list takes the user to that section of the tree.

p-0034In one embodiment, lightweight modeling of the user's interest can be used to inform the layout and presentation of the hierarchical data structure. User interest can be modeled using a Degree-Of-Interest (DOI) function that assigns a value representing the estimated relative interest of the user to each node in the structure. Computed degree-of-interest values, as well as any other interest characteristic, can be used to affect the layout of the hierarchical data structure when it is visualized.

p-0035In one embodiment, a multi-focal degree-of-interest function can assign a maximal degree-of-interest to focus-nodes and their parent nodes, up to the root of the tree. Degree-of-interest values for the remaining nodes then decrease as a function of distance from the nodes having higher degree-of-interest. Because nodes below a particular degree-of-interest threshold will not be visualized, the degree-of-interest calculation can be stopped at “disinterest threshold” boundaries, thus bounding computation time to only the number of possibly visualized nodes.

p-0036Once the focus+context engine has assembled a hierarchical data structure of potentially visualized nodes where each node includes a respective node interest characteristic (such as a degree-of-interest value, a rank, a priority, or classification), it provides the resulting hierarchical data structure to the layout process. The layout process is subsequently described.

p-0037A layout process <b>400</b> uses two data structures that are described with respect to <figref idrefs="DRAWINGS">FIG. 3</figref> and <figref idrefs="DRAWINGS">FIG. 2</figref>. One skilled in the art will understand that these data structures are but one of many equivalent data structures that can be used in procedural, object-oriented, or other programming methodologies

p-0038<figref idrefs="DRAWINGS">FIG. 2</figref> illustrates a ‘depth level’ data structure <b>200</b> that maintains the height in display coordinates of the depth levels associated with the hierarchical data structure. There are two types of fields in the ‘depth level’ data structure <b>200</b> as represented by a ‘height for primary depth level 1’ field <b>201</b> and a ‘heights for secondary depth levels off of primary depth level 1’ field <b>203</b>. Similar fields exist in the ‘depth level’ data structure <b>200</b> for each depth level (for example a ‘height for primary depth level 2’ field <b>205</b> and a ‘heights for secondary depth levels off of primary depth level 2’ field <b>207</b>. A primary depth level contains at least one focus-node or contains a node that is a direct child node of a focus-node. The primary depth levels contain a value that represents the height of the specified level of portion of the hierarchical data structure that may be visualized. The values in the secondary depth level fields contain the heights of the corresponding child branches of the hierarchical data structure that does not contain a focus-node.

p-0039In some embodiments, entries in the ‘depth level’ data structure <b>200</b> can be accessed using a registry and a key system, a linked list, or any other storage structure known to one skilled in the art now or in the future.

p-0040<figref idrefs="DRAWINGS">FIG. 3</figref> illustrates a ‘space list’ entry <b>300</b> that can be accessed' from a space list structure. The space list structure provides access to the blocks that will be used to position and visualize the hierarchical data structure that is provided to the layout process <b>400</b>. The ‘space list’ entry <b>300</b> contains a ‘pointer to root node for block’ field <b>301</b> that points to the parent node in the hierarchical data structure. A ‘block breadth’ field <b>305</b> maintains the breadth of the block representation (including any secondary block representations contained within the block representation—secondary block representations generally do not enclose other block representations and so simply contain the breadth of the secondary block representation itself). In one embodiment, the value contained in a ‘block position’ field <b>307</b> represents the horizontal coordinate for the left most edge of the block. Each block spans the secondary depth levels within its primary depth level. In one embodiment, blocks span a single primary depth level. The blocks are indexed by their depth level in the space list, while the depths of subtrees are indexed by their sub-level, as depicted by the markers at the top of the figure. This segregation allows each depth level of the hierarchical data structure to be separately considered with respect to space constraints and positioning, in turn enabling a flexible handling of multiple foci. The ‘depth level’ data structure <b>200</b> and the space list are mapped using methods known to one skilled in the art (for example, but without limitation, by the use of a hashmap structure).

p-0041<figref idrefs="DRAWINGS">FIG. 4</figref> illustrates the layout process <b>400</b> that can be invoked to prepare a hierarchical data structure for display within a constrained display area that has a constrained breadth extent and a constrained depth extent. The layout process <b>400</b> initiates at a start terminal <b>401</b> and continues to a ‘receive hierarchical data structure’ procedure <b>403</b> that receives the hierarchical data structure. The hierarchical data structure contains information that can be presented within a constrained display area. The constrained display area has a constrained depth extent and a constrained breadth extent. The hierarchical data structure includes a number of nodes, each of which contain a respective node interest characteristic that can be a degree-of-interest value. The constrained display area can be a view in a window or otherwise dimensioned area intended for the presentation of the visualized portion of the hierarchical data structure.

p-0042The first phase of the layout process <b>400</b> computes the space taken by the hierarchical data structure in the absence of any display constraints and simultaneously segments the hierarchical data structure into a block structure to simplify subsequent layout calculations. One result of this phase is an initial layout of the hierarchical data structure assuming an unconstrained display area and that the entire hierarchical data structure is to be visualized. The initial layout provides an initial breadth extent value and an initial depth extent value. The first phase also populates the ‘depth level’ data structure <b>200</b> and the ‘space list’ entry <b>300</b> and thus creates a block representation of the hierarchical data structure.

p-0043A ‘construct block representation of the hierarchical data structure’ procedure <b>405</b> performs the first pass through the hierarchical data structure, computes the initial layout and segments the hierarchical data structure into a block representation that is an abstraction of the hierarchical data structure as is subsequently described with respect to <figref idrefs="DRAWINGS">FIG. 5</figref>.

p-0044The second phase of the layout process <b>400</b> compares the initial breadth extent and the initial depth extent against the bounds of the display area (the constrained depth extent and the constrained breadth extent). If the initial depth extent and the initial breadth extent do not exceed the available display area, the initial layout is presented on the display area.

p-0045However, if either of the initial depth extent or the initial breadth extent exceeds the bounds of the display area, the layout of the hierarchical data structure must be reduced from that of the initial layout.

p-0046A ‘depth constrained’ decision procedure <b>407</b> determines whether the initial depth extent of the hierarchical data structure is greater than the constrained depth extent for the display. If the initial depth extent is not greater than the constrained depth extent the layout process <b>400</b> continues to a ‘breadth constrained’ decision procedure <b>409</b> that determines whether the initial breadth extent is greater than the constrained breadth extent. If the initial breadth extent is not greater than the constrained breadth extent, all the block representations are known to fit within the constrained breadth extent and the layout process <b>400</b> continues to an ‘allocate breadth space for depth level’ procedure <b>410</b> to actually position the block representations within the constrained breadth extent as is subsequently described with respect to <figref idrefs="DRAWINGS">FIG. 8</figref>. Once the block representation are positioned, an ‘assign coordinates for visualized nodes’ procedure <b>411</b> assigns display coordinates for each block and visualized node. A ‘present visualization’ procedure <b>412</b> then presents the visualized nodes (and/or the block representation visualization) such as on a display device, printer, or by storage in file. The layout process <b>400</b> completes through an end terminal <b>413</b>.

p-0047If the ‘depth constrained’ decision procedure <b>407</b> determines that the initial depth extent is greater than the constrained depth extent, the layout process <b>400</b> continues to a ‘position to most recent focus-node’ procedure <b>415</b> that first locates the block representation that includes the most recently selected focus-node and its siblings and positions the visualization such that the siblings of the focus-node are within the display area. Some of the depth levels that include ancestor blocks of the focus-node may be elided from the detailed visualization and located in an elided depth level trail representation. The elided depth level trail representation of the elided ancestors helps the user maintain context within the visualization and to provide immediate access to the ancestral levels of the hierarchical data structure. This approach can be used separately from, or in conjunction with, prior art techniques for scaling, scrolling, or panning the initial layout to fit within the display area. (Excessive scaling, however, eventually destroys the legibility of displayed information.)

p-0048In one embodiment, the positioning is determined by counting how many depth levels, starting from the root, must be removed to allow the user-selected focus-node and its children to fit into the center of the display area.

p-0049In one embodiment, hysteresis logic is used to control undue disruption of the visualization due to location changes in the visualization of the focus-node that can result as the user browses a group of siblings with descendants of shifting depth requirements.

p-0050In the case of excessive breadth, aggregation can be applied in addition to, or in lieu of, scaling. For a given depth level with excessive breadth, aggregation elides the nodes of lowest interest until the breadth of the depth level is sufficiently reduced to fit within the constrained breadth extent of the display area. Elided nodes can be represented by an aggregate visualization (see <figref idrefs="DRAWINGS">FIG. 10</figref> and its description).

p-0051If the ‘breadth constrained’ decision procedure <b>409</b> determines that the initial breadth extent for all the block representations is greater than the constrained breadth extent, the layout process <b>400</b> continues to an ‘aggregate nodes’ procedure <b>417</b> that aggregates the less interesting nodes as is subsequently described with respect to <figref idrefs="DRAWINGS">FIG. 7</figref>. This second path through the hierarchical data structure enforces space constrains imposed by the constrained breadth extent and the constrained depth extent.

p-0052After the ‘aggregate nodes’ procedure <b>417</b>, the layout process <b>400</b> continues to the ‘allocate breadth space for depth level’ procedure <b>410</b> for processing as previously described.

p-0053In the final phase of the layout process <b>400</b>, the block representation and information from the visualized subset of nodes are assigned their screen co-ordinates by an ‘assign coordinates for visualized nodes’ procedure <b>411</b>. This pass iterates through each depth level from the root of the hierarchical data structure down, at each level first determining the position of the block representations and then laying out the nodes that each block representation contains with respect to the visualization of the block representation. Iterating through depth levels visits nodes in a breadth-first fashion, ensuring that parent nodes have their positions assigned before children blocks are considered. Once the display coordinates for the block representations and nodes are determined, a ‘present visualization’ procedure <b>412</b> presents the visualization of the hierarchical data structure (for example, on a display device such as a one or more monitors or printers; or stores the visualization as data in computer-readable storage for later playback and presentation). After the information is presented, the layout process <b>400</b> completes through an end terminal <b>413</b>.

p-0054<figref idrefs="DRAWINGS">FIG. 5</figref> illustrates a ‘construct block representation of the hierarchical data structure’ process <b>500</b> that can be invoked after the ‘receive hierarchical data structure’ procedure <b>403</b>, that initiates at a start terminal <b>501</b>, and continues to an ‘initialize space list and depth levels structures’ procedure <b>503</b>. The ‘construct block representation of the hierarchical data structure’ process <b>500</b> constructs a block representation of the hierarchical data structure that includes a number of block descriptors that are associated with the depth levels and computes the initial breadth extents and the initial depth extents needed to present the entire hierarchical data structure in the absence of any constrained display area considerations (the initial layout) as well as a respective depth level breadth extent for each depth level. This process simultaneously segments the hierarchical data structure into a block representation specified by the ‘depth level’ data structure <b>200</b> and the space list that contains entries such as the ‘space list’ entry <b>300</b>. The block representation simplifies subsequent layout calculation.

p-0055The ‘initialize space list and depth levels structures’ procedure <b>503</b> initializes the space list and the ‘depth level’ data structure <b>200</b> as well as any other required initialization. After the data structures are initialized, an ‘invoke recursive extent function’ procedure <b>505</b> recursively traverses the hierarchical data structure to create an initial layout and to calculate the initial breadth extent and the initial depth extent that would be required to present the initial layout of the hierarchical data structure. In addition, a block representation of the hierarchical data structure is created in the space list (using entries such as the ‘space list’ entry <b>300</b>) in association with the ‘depth level’ data structure <b>200</b>. The result of the ‘construct block representation of the hierarchical data structure’ process <b>500</b> is the generation of the breadth and depth, in pixels, of the unconstrained hierarchical data structure layout, and an aggregated block representation of the hierarchical data structure.

p-0056<figref idrefs="DRAWINGS">FIG. 6</figref> illustrates a ‘recursive extent’ function <b>600</b> that can be invoked by the ‘invoke recursive extent function’ procedure <b>505</b>. The ‘recursive extent’ function <b>600</b> performs a depth-first traversal of the hierarchical data structure and computes the breadth and depth requirements for each block representation and its group of siblings. The ‘recursive extent’ function <b>600</b> also maintains global data structures representing the depth requirements for each level of the hierarchical data structure. This allows depth requirements for particular levels of the hierarchical data structure to be dynamically computed across different branches of the hierarchical data structure.

p-0057The ‘recursive extent’ function <b>600</b> initiates at a start terminal <b>601</b> and continues to a ‘recursively determine extents for each non-focus branch’ procedure <b>603</b> that computes the maximum depth for each branch of the hierarchical data structure that does not include a focus-node. It does this by storing depth calculations for each secondary depth level while calculating breadth values for each node that is not a focus-node. Next, a ‘recursively determine extents for each focus branch’ procedure <b>605</b> computes the maximum height for each branch that contains a focus-node and calculates the breadth values for each primary block. In addition, the ‘recursive extent’ function <b>600</b> computes the maximum height for the current depth level as the maximum of the focus-node heights for all the non-focus branches and calculates the height for the primary depth level. In addition, the ‘recursive extent’ function <b>600</b> maintains the maximum breadth global.

p-0058A ‘focus-node’ decision procedure <b>607</b> determines whether the node is a focus-node. If not the ‘recursive extent’ function <b>600</b> returns the calculated breadth of the node through a ‘return breadth’ function terminal <b>609</b>. If the node is a focus-node, the ‘recursive extent’ function <b>600</b> continues to a ‘create new space list entry’ procedure <b>611</b> that allocates and enters an entry such as the ‘space list’ entry <b>300</b> to the space list (thus, defining a new block representation).

p-0059One skilled in the art will understand that the programmed-function represented by the flowchart illustrated in <figref idrefs="DRAWINGS">FIG. 6</figref> recursively calls itself. One skilled in the art, having access to <figref idrefs="DRAWINGS">FIG. 6</figref> and the associated descriptions herein will be able to practice this embodiment without undue experimentation.

p-0060Aggregates are computed by sorting all the nodes in the given depth level by the value of their respective node interest characteristic (for example, a degree-of-interest value), then sequentially removing the lowest-interest nodes and updating size calculations until the visualization of the block representations in the depth level will fit within the constrained breadth extent. Since the lowest-interest nodes may be dispersed throughout the given depth level, this requires some book-keeping of elided nodes, and updating size calculations when adjacent nodes are marked for aggregation.

p-0061<figref idrefs="DRAWINGS">FIG. 7</figref> illustrates an aggregate nodes' process <b>700</b> that can be invoked by the ‘aggregate nodes’ procedure <b>417</b>, that initiates at a start terminal <b>701</b>, and continues to a ‘for each depth level’ iteration procedure <b>703</b> that iterates over each depth level. Once all the depth levels are iterated, the aggregate nodes' process <b>700</b> completes through the end terminal <b>705</b>.

p-0062For each iterated depth level, a ‘breadth of depth level>constrained breadth extent’ decision procedure <b>707</b> determines whether depth level breadth extent required by the block representations in the iterated depth level (the depth level breadth extent) exceeds the constrained breadth extent. If not, the aggregate nodes' process <b>700</b> continues to the ‘for each depth level’ iteration procedure <b>703</b> to iterate the next depth level.

p-0063If the depth level breadth extent (the sum of the breadth of the blocks in the depth level) exceeds the constrained breadth extent, the aggregate nodes' process <b>700</b> continues to the ‘sort nodes by increasing interest’ procedure <b>709</b> that sorts the nodes in the depth level by their respective node interest characteristic.

p-0064Next, an ‘aggregate nodes until breadth&lt;maximum space’ procedure <b>711</b> iterates through the set of nodes in the hierarchical data structure that are in the iterated depth level and marks those nodes that have a lower interest characteristic as belonging to the elided subset (“not visible” subset) until the depth level breadth extent fits within the constrained breadth extent. The remaining nodes are members of the visualized subset. While any appropriate partitioning mechanism can be used to partition the subset of nodes in the depth level, in one embodiment, a Boolean array is created that represents whether a corresponding node is elided. Then, the Boolean array is examined for appropriate true/false runs to determine where an aggregation node is to replace two or more adjacent siblings.

p-0065Once all the nodes on the depth level have been processed, iterate through the elided nodes in order. For each run of elided nodes (two or more adjacent siblings marked as elided) disable visualization of the node, and where appropriate replace the run of elided nodes with an aggregated node and add the aggregated node to the visualized subset. Update the value of the ‘block breadth’ field <b>305</b> in the corresponding ‘space list’ entry <b>300</b> accordingly.

p-0066<figref idrefs="DRAWINGS">FIG. 8</figref> illustrates an ‘allocate breadth’ process <b>800</b> that can be invoked by the ‘allocate breadth space for depth level’ procedure <b>410</b>. The visualization of a child block representation (or the nodes associated with it) is preferably located underneath (in the depth direction) their parent's block representation visualization. Due to the constrained display area this is not always possible. Nevertheless, it is useful to minimize the distance between parents and children. One embodiment uses a greedy optimization algorithm, for the most common situation, that processes block representations within a depth level from the “outside-in,” beginning with block representations having visualizations nearest the edges of the constrained display area and centering them under their parents without exceeding the constrained breadth extent or overlapping. Then the amount of space needed for the remaining block representations in the depth level is determined. If sufficient space does not exist for visualizing the remaining block representations the optimization algorithm pushes the visualizations of the current block representations towards the boundaries of the constrained display area as necessary to free the required space. The distance each block representation visualization is moved is proportional to its breadth because larger blocks can move further and still be directly underneath (though not centered under) their parent block. This process is then repeated for the pair of blocks adjacent to the previous ones, until either all blocks have been positioned or there is only a single block left (in which case, we simply place the block within the remaining space, aligning its center as close as possible to its parent).

p-0067The ‘allocate breadth’ process <b>800</b> initiates at a start terminal <b>801</b> and continues to a ‘for each depth level’ iteration procedure <b>803</b> that iterates each depth level. Once all the depth levels have been iterated, the ‘allocate breadth’ process <b>800</b> completes through the end terminal <b>805</b>.

p-0068As each depth level is iterated, a ‘single block in level’ decision procedure <b>807</b> determines whether the-depth level includes only one-block representation. If so, the ‘allocate breadth’ process <b>800</b> continues to a ‘center under parent’ procedure <b>809</b> that centers the visualization of the block representation under its parent visualization (subject to boundary conditions and the probation against overlapping visualizations). The ‘allocate breadth’ process <b>800</b> returns to the ‘for each depth level’ iteration procedure <b>803</b> for the next iteration.

p-0069If the depth level has more than one block representation, the ‘allocate breadth’ process <b>800</b> continues to a ‘blocks fill breadth’ decision procedure <b>811</b> that determines whether the visualizations of the block representation in the depth level fill the entire breadth. If so, the ‘allocate breadth’ process <b>800</b> continues to an ‘abutting blocks’ procedure <b>813</b> that places visualizations of the block representations adjacent to each other, and then the ‘allocate breadth’ process <b>800</b> continues to the ‘for each depth level’ iteration procedure <b>803</b> for the next iteration.

p-0070If the depth level has more than one block representation and yet does not fill the entire breadth, the ‘allocate breadth’ process <b>800</b> continues to a ‘distribute blocks over breadth’ procedure <b>815</b> that first centers the visualizations of the first and last block representations in the depth level under their parent block visualizations (but not overlapping and not extending outside of the display area for the visualization). If there is not enough space between the two blocks for the rest of the blocks, put the current blocks towards the edges of the display until there is enough space. Then recursively repeat for the next outermost block representations with the new currently-available free breadth.

p-0071Once the blocks for a given level have been positioned, the provided bounds are used to position the nodes and aggregates within the blocks by a depth-first traversal of the block content. <figref idrefs="DRAWINGS">FIG. 9</figref> illustrates a presentation process <b>900</b> that can be used to present the information from the visualized nodes and aggregated nodes, that can be invoked by the ‘present visualization’ procedure <b>412</b> of <figref idrefs="DRAWINGS">FIG. 4</figref>, that initiates at a start terminal <b>901</b>, and that continues to a ‘for each visualized element’ iterative procedure <b>903</b> that iterates over each visualized node, aggregate, and optionally each block representation.

p-0072As each node is iterated, a ‘present node information’ procedure <b>905</b> presents the information contained by the visualized node or aggregated node. In addition, an ‘optional present block information’ procedure <b>907</b> can be conditioned to optionally present the outline of the block representation. Once the information in the visualized elements is presented, the presentation process <b>900</b> continues back to the ‘for each visualized element’ iterative procedure <b>903</b> to iterate the next element. When all the elements have been iterated, the presentation process <b>900</b> continues to a ‘for each connected parent-child node’ iterative procedure <b>909</b> that iterates each parent node and child node combination to provide a spline connector between the parent and child nodes.

p-0073As each parent/child node combination is iterated, an ‘optional avoidance’ procedure <b>911</b> can be called to specify spline points and/or adjust spline point tension and bias parameters such that the resulting splined connectors between the parent and child nodes tend to avoid areas that include an extent of any block representation. If no special parameters are provided by the ‘optional avoidance’ procedure <b>911</b>, the presentation process <b>900</b> can use a formulistic spline parameterization that can be heuristically determined.

p-0074One such spline parameterization first sets spline end points at the center of the opposing edges of the visualized parent node and the visualized child node. A first spline point can be added approximately ⅔ of the depth distance from the parent's spline end point and inline with that point. A second spline point can be added approximately ⅞ of the depth distance from parent's spline end point and ⅞ of the breadth distance from the parent's spline end point.

p-0075A ‘present spline’ procedure <b>913</b> then presents the iterated connector between the visualizations of the parent and child nodes. When all the visualized node connectors have been iterated, the presentation process <b>900</b> continues to a ‘present elided depth levels’ procedure <b>915</b> that visualizes the elided depth level trail and completes through an end terminal <b>917</b>.

p-0076<figref idrefs="DRAWINGS">FIG. 10</figref> illustrates an example visualization image <b>1000</b> that can be generated by application of the disclosed technology. In this example, an elided depth level trail area <b>1001</b> contains representations of the ancestor depth levels of a most recent focus-node <b>1003</b>. The elided depth level trail area <b>1001</b> is visualized outside of a constrained display area <b>1004</b>. To help the reader understand how depth levels are associated with the visualization, a depth level indicator <b>1005</b> is provided on the example visualization image <b>1000</b>. However, such an indicator would not generally be needed for the visualization. A block visualization <b>1007</b> can be included within the constrained display area <b>1004</b>. As has been discussed, an aggregate visualization <b>1011</b> indicates elided nodes. The existence of subtrees descending from secondary depth levels can be marked by a subtree indicator <b>1013</b>. A pegged node visualization <b>1015</b> can be indicated by a color, or other highlighting mechanism.

p-0077One skilled in the art will understand that the layout process <b>400</b> can be invoked by: a call by a computer program, making the hierarchical data structure available to a program, task, process, thread, programmed-function, programmed-procedure, method, object, hardware device, or any combination thereof currently in existence or to be developed.

p-0078One skilled in the art will understand that one embodiment hierarchical data structure layout algorithm that supports the display of single or multi-focal trees within bounded space constraints. Together, these features allow interactive visualization at animation rates with hierarchical data structure structures on the order of million nodes while making the most of the available screen real estate.

p-0079One skilled in the art would understand that the block representations need not be visualized and that significant performance advantage accrue by the use of the block representation when performing the aggregation and layout functions for the visualized nodes for multi-focal presentation of the hierarchical data structure.

p-0080One skilled in the art will understand that the procedures discussed herein can be implemented in electronic or other circuitry or logic, as well as implemented by the use of a programmed computer or data processor. Such a one will also understand that the methods described herein and their equivalents can be implemented using procedural, object-oriented, or other programming-methodologies.

p-0081One skilled in the art will understand that the technology disclosed herein is a very efficient layout algorithm for hierarchical data structures.

p-0082Both empirical and theoretical analyses confirm the efficiency of the layout process <b>400</b> that computes a space-constrained, multi-focal layout in nearly linear running time, bounded from above by n log n, where n is the number of visible nodes prior to aggregation. Both the first and third passes made by the algorithm are linear, as they involve a single walk through the hierarchical data structure and the node size computation and hierarchical data structure segmentation routines run in constant time. The point at which non-linear complexity is introduced is during the second pass, if and when aggregation occurs, requiring the n log n operation of sorting the nodes in a given depth level. However, this rarely includes the whole visualized structure, making the common case less costly than the upper bound might imply. In actual usage, rendering bottlenecks slow the systems performance long before the computational burden of the layout process <b>400</b> becomes an issue.

p-0083Although the technology has been described in terms of the presently preferred embodiments, one skilled in the art will understand that various modifications and alterations may be made without departing from the scope of the claims. Accordingly, the scope of the claims is not to be limited to the particular embodiments discussed herein.