Computer graphics processing and selective visual display system – Display driving control circuitry – Controlling the condition of display elements
Reexamination Certificate
1999-04-19
2002-04-23
Nguyen, Cao H. (Department: 2173)
Computer graphics processing and selective visual display system
Display driving control circuitry
Controlling the condition of display elements
C345S215000
Reexamination Certificate
active
06377287
ABSTRACT:
TECHNICAL FIELD
The invention relates generally to navigating within large hyperbolic space and more particularly to methods and systems for reducing the display cluttering and complexity of navigating within large hierarchies such as organizational charts or Internet resources.
BACKGROUND OF THE INVENTION
Recently, there has been substantial research focused on visual mining of large hierarchies of nodes, such as the World Wide Web structure, organization charts, and file systems, using a hyperbolic tree space. For example, in Web data mining, there is an immediate need for users to visualize the content and usage of the Web. How to navigate through millions of documents to access information on one display is a problem which needs to be solved. Hyperbolic space provides an elegant solution to displaying large hierarchies on a user screen. Hyperbolic space is different from the conventional approaches of laying trees on an Euclidean space. In Euclidean space, the area of a circle which contains nodes grows linearly. In hyperbolic spaces, the area of a circle grows exponentially with respect to its radius. As a result, known approaches using hyperbolic space can handle a graph of over 20,000 documents on the Web, using a focus-and-context scheme.
Hyperbolic space allows a user to navigate through the nodes of a large hierarchy and to view the relationship of the visible portion of the space to the entire structure on a single display. This is an improvement over techniques in which multiple displays are required to represent a large amount of data sets, with the user having to click through display after display in order to find the information that is needed.
In a directed hierarchical hyperbolic tree, nodes are organized along parent and child relationships. A parent can have many children. A child can have only one parent. For example, in an organization chart hyperbolic tree, each employee reports to one manager. A manager may have many employees. However, in practice this may not be sufficient, since an employee may report to two managers (e.g., one regular manager and one temporary project manager). Thus, two paths may be needed, one for the regular manager and the other for the temporary project manager.
In a customer support application, a hyperbolic tree may be used to organize large numbers of questions and answers in a hierarchical structure. Questions are parent nodes, while answers are arcs (pointers) to child nodes. A question can have several answers. An answer can lead to more questions and answers. However, it is sometimes necessary for an answer to link to another question-and-answer group (sub-tree) which does not directly belong to the hierarchical hyperbolic space.
In a directed non-cyclic hierarchical hyperbolic space, a node (except for a root node) has exactly one primary parent. If a node has more than one parent, then exactly one is designated as the “primary parent” and the others are referred to as “secondary parents.” The link from a node's secondary parent to the node is referred to as a “secondary path.” The path from a node's primary parent to the node is referred to as the “primary path.” For example, the path to the regular manager is a direct hierarchical link, called the primary path. The path to the temporary project manager is a directed non-hierarchical link, called the secondary path. A node which serves as a multi-path node contains both the primary path and the secondary path.
In the above examples, a secondary path is needed to represent the relationship between the employee and the employee's temporary project manager or to relate a particular answer with other question-and-answer groups. A concern is that strict hierarchical tree structures are too restrictive, since often a relationship needs to link different branches of the tree. Commercially available hyperbolic tree implementations do not support such secondary paths. One solution would be to depict the secondary relationships with additional lines. However, this solution could introduce thousands of lines and intersections, as will be explained with reference to
FIG. 1
, which includes only primary relationships, and
FIG. 2
, which includes both primary and secondary relationships. Also, for far away nodes that are off the screen, it would introduce “broken” lines that do not terminate in a node on the current display. As a result, the hyperbolic space becomes very cluttered and difficult to visualize.
With reference to
FIG. 1
, a conventional tree structure
10
is shown as having a root node
12
that is labeled “MS PRODUCTS.” The root node includes eight child nodes
14
,
16
,
18
,
20
,
22
,
24
,
26
and
28
that are connected to the parent node by edges (i.e., primary paths)
30
,
32
,
34
,
36
,
38
,
40
,
42
and
44
, respectively. Each of the child nodes is the parent node to at least one other node. For example, the child node
20
labeled “OFFICE PRODUCTS” is the parent node for six other nodes
46
,
48
,
50
,
52
,
54
and
56
that are connected to the node
20
by primary paths. In the hyperbolic space, the far away nodes and edges are diminished when the user is not focusing on them. These nodes will reappear when the user warps the display to focus on or near them. The user can dynamically warp the display to focus on thousands of different nodes for navigation. The conventional tree of
FIG. 1
is a non-cyclic hierarchical hyperbolic structure without secondary paths. Thus, the structure will include n nodes and n−1 edges.
FIG. 2
is an illustration of the same tree, but with secondary paths in addition to the primary paths. The multi-path hyperbolic tree includes numerous lines and intersections. There are also many broken lines. As can be seen, the hyperbolic tree becomes very cluttered. The cluttering is increased if additional secondary paths are necessary in order to show all of the relationships. In the illustration of
FIG. 2
, there are n nodes, n−1 primary edges and numerous secondary edges and intersections.
What is needed is a system and method for visualizing and navigating through a complex hyperbolic space with multiple paths, such as a web-based hyperbolic space, while preserving the simplicity of nodes organized along parent and child relationships.
SUMMARY OF THE INVENTION
A system and a method in accordance with the invention utilize hidden links, mapping, and unmapping to enable single-screen visualization of a directed non-cyclic hyperbolic space with multiple path links. The hidden links technique hides all of the secondary paths in each node's property at the time that the hyperbolic space is initialized. The nodes to which a secondary path are pointed become accessible and interactive via the secondary path only at the time of focus upon portions of the hyperbolic space related to the secondary path. The user can easily navigate through all possible paths without tracing many lines and intersections.
In the preferred embodiment, the hyperbolic space is organized in a directed non-cyclic hierarchical space. Thus, there is a primary graph which links all of the nodes in a tree form that follows the one parent per child convention. These links are primary tree links. However, there are also secondary links that define a highly connected graph. A node in the hierarchy can have one incoming primary link (i.e., one link from a primary parent node) and may have many secondary links. The secondary paths are hidden at the time that the hyperbolic space is initialized.
A “primary path” is defined herein as a tree link. Preferably, it is a directed non-cyclic graphic link in a hierarchical hyperbolic space. With the exception of a root node, each node has one primary parent, with the link from a node's primary parent to that node being the primary path. A “secondary path” is defined as a link in which additional (i.e., secondary) parents are defined. The link from a node's secondary parent to that node is a secondary path. A “hidden-link node” (as referred to as a “multi-path node”) is defi
Dayal Umeshwar
Hao Ming C.
Hsu Meichun
Krug Adrian
LandOfFree
Technique for visualizing large web-based hierarchical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Technique for visualizing large web-based hierarchical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Technique for visualizing large web-based hierarchical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896974