Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-04-17
2002-04-09
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S215000, C707S793000
Reexamination Certificate
active
06369819
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This Application is related to the following Applications, which were filed of even date herewith:
(1) “Usage Based Methods of Traversing and Displaying Generalized Graph Structures,” by Ed H. Chi, et al., Ser. No. 09/062,341; and
(2) “Methods for Interactive Visualization of Spreading Activation Using Time Tubes and Disk Trees,” by Peter L. T. Pirolli, et al., Ser. No. 09/062,540.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is related to the field of displaying a related series of generalized graph structures. Specifically, the present invention is related to displaying changes over time of structure and parameters of a generalized graph structure, and the present invention is related to displaying relationships between the related series of graphs. The present invention addresses the problem of coherently displaying the changes in structure, content, and usage of World Wide Web pages of a web site.
2. Discussion of the Related Art
The World-Wide Web (“web”) is perhaps the most important information access mechanism to be introduced to the general public in the 20th Century. As larger numbers of organizations rely on the Internet to distribute information to potential consumers and investors, they also realize its potential for distributing and organizing large volumes of data for later retrieval by employees and business partners. A company's web site is rapidly becoming one of its most important business investments.
As an information repository, a web site generally receives a high amounts of usage. Web site usage patterns that are derived by monitoring the how the company's employees use its web site enhance the companies understanding of its business activities. For example, monitoring what product literature the sales force is downloading may be a way to forecast sales. In short, traditional market analysis can be applied to this information resource.
Analysts are interested in not just how the web pages are used, but as well as the context under which they are placed, such as the linkage structure and the web page content. A web site is a dynamic structure, because its topology as evidenced by its linkage structure, the contents of its pages, and its usage changes continually. Analysts want to be able to analyze the evolving web site.
Because of analysts increasing desire to discover and understand users'access patterns, relationships between web page contents, and to efficiently structure web sites'topology, a need exists for a set of visualization tools which aid in the process of web site analysis.
The topology, content, or usage of a web site may be modeled at any given time as a generalized graph structure having various parameters associated with the various nodes and/or links. In order to enable effective cognitive processing of the changes over time in a web site, a need exists for displaying the change over time in a coherent manner to a web site designer, administrator, or analyst.
SUMMARY OF THE INVENTION
A conventional technique for understanding a graph structure is to display a representation of the links and nodes which constitute the graph structure. One view of the World Wide Web is that of a graph structure, with web pages representing nodes and hyperlinks representing the links between the nodes. The various pages which make up a web site frequently change over time in structure, usage, and content. The structure, usage, and content of the web pages in a web site at any given time may be modeled as a graph. An object of the present invention is to provide a method for displaying in a coherent manner the changes over time of a web site's structure, usage, and content.
According to the present invention, time tubes are generated by a method of displaying a related series of graphs. Time tubes according to the present invention are especially well suited for use as a web site analysis tool. Although the usefulness of time tubes according to the methods of the present invention is illustrated using the example of web site analysis, the methods are applicable to all fields involving evolving graph structures. For example, telecommunication systems, physical transport systems, such as highways, trains, and the like, and manufacturing systems can all be modeled as graphs and analyzed using time tubes.
Time tubes illustrate changes in a graph that undergoes one or more transformations from one state to another. In the preferred embodiment, the transformations are displayed using the length of the cylindrical tube, filling the length of the time tube with planar slices which represent the data at various stages of the transformations. Time tubes may encode several dimensions of the transformations simultaneously by altering the representation of size, color, and layout among the planar slices which make up the time tube.
Examples of the transformations that time tubes can display include, but are not limited to, temporal, value-based, and spatial transformations. Temporal changes occur when web pages are added or deleted over time. Value-based changes include node colors, which may be used to encode a specific page's usage parameter, as measured by its visitation rate. Spatial changes include the scaling of physical dimension as graphs expand or contract in size.
According to the present invention, the states of a graph at various times are represented as a series of related graphs. The same nodes may exist in some or all of the graphs. According to the preferred embodiment the method of displaying the related series of graphs, an inventory of all existing nodes is performed so as to generate a list of all nodes that have existed at any time. This inventory is used to produce a layout template in which each unique node is assigned a unique layout position. To produce each planar slice, the specific nodes which exist in the slice are placed at their respective positions assigned in the layout template. Then the planar slices are displayed.
In another aspect of the present invention, corresponding nodes in planar slices are linked, such as with translucent streamlines. In the preferred embodiment of the present invention, this linking is performed in response to a user selecting a node in a planar slice by placing his cursor over the selected node, such that the nodes in other planar slices corresponding to the user's selected node are displayed. This linking also may be performed so as to show clustering of two or more nodes in one planar slice into a single node in an adjacent planar slice.
Furthermore, because a time tube is a cylindrical log, it can be rotated along its central axis to move specific nodes closer to the user's viewpoint. Because time tubes exist in a three dimensional work space, the user can change his viewing perspective for time tube, such as zooming into or out of an area of interest.
These and other features and advantages of the present invention are apparent from the Figures as fully described in the Detailed Description of the Invention.
REFERENCES:
patent: 5619632 (1997-04-01), Lamping et al.
patent: 5644736 (1997-07-01), Healy et al.
patent: 5815161 (1998-09-01), Emmerink et al.
patent: 5877766 (1999-03-01), Bates
patent: 6002401 (1999-12-01), Baker
patent: 6054989 (2000-04-01), Roertson et al.
patent: 6151595 (2000-11-01), Pirolli et al.
patent: 6154213 (2000-11-01), Rennison et al.
patent: 6222559 (2001-04-01), Asano et al.
patent: 6223145 (2001-04-01), Hearst
patent: WO 97/31319 (1997-08-01), None
Stasko et al., “Software Visualization: Programming as a Multimedia Experience”, 1998, Massachusetts Institute of Technology.*
Carriere, Jeromy and Kazman, Rick, “Research Report: Interacting with Huge Hierarchies: Beyond Cone Trees,” Proceedings of Information Visualization Symposium, Oct. 30-31, 1995, Atlanta Georgia, pp. 74-81.
Hill, William and Holland, Jim, “Edit Wear and Read Wear,” Proceedings of CHI, 1992, pp. 3-9.
Lamping, John and Rao, Ramana, “Laying Out and Visualizing Large Trees Using a Hyperbolic Space,” Pro
Card Stuart K.
Chi Ed H.
Gossweller Rich
Mackinlay Jock D.
Pirolli Peter L. T.
Fliesler Dubb Meyer & Lovejoy LLP
Harrison Chante
Luu Matthew
Xerox Corporation
LandOfFree
Methods for visualizing transformations among related series... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for visualizing transformations among related series..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for visualizing transformations among related series... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2869567