Browse Prior Art Database

Insertion and Reading Algorithms for Visualization

IP.com Disclosure Number: IPCOM000112714D
Original Publication Date: 1994-Jun-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 164K

Publishing Venue

IBM

Related People

Lehr, TF: AUTHOR

Abstract

An earlier publication (*) describes a data structure and insertion algorithm for visualizing event-driven traces containing asynchronous events in the PieScope (originally written by Professor Zary Segall of Carnegie Mellon University) trace visualization tool. The algorithm is designed for use by visualization tools like PieScope which employ Ghant charts (bars) as the chief means of representing event-pairs. This algorithm contains a number of rules for deciding how to display the events. As the disclosure explains, it is more powerful than algorithms for other trace visualization tools in that it can portray event hierarchies as well as asynchronous events. The algorithm permits the tool to visualize an entire trace or only selected parts of a trace.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 34% of the total text.

Insertion and Reading Algorithms for Visualization

      An earlier publication (*) describes a data structure and
insertion algorithm for visualizing event-driven traces containing
asynchronous events in the PieScope (originally written by Professor
Zary Segall of Carnegie Mellon University) trace visualization tool.
The algorithm is designed for use by visualization tools like
PieScope which employ Ghant charts (bars) as the chief means of
representing event-pairs.  This algorithm contains a number of rules
for deciding how to display the events.  As the disclosure explains,
it is more powerful than algorithms for other trace visualization
tools in that it can portray event hierarchies as well as
asynchronous events.  The algorithm permits the tool to visualize an
entire trace or only selected parts of a trace.  When the tool
attempts to visualize only part of a trace, the algorithm prevents
the tool from visualizing asynchronous events which begin earlier
than the period being examined but finish in that period.  Thus,
although the events are present in the trace, they are missed by the
algorithm.  The invention disclosed here corrects for these
omissions.

      Improvement of Insertion Algorithm for Visualization - The data
structure described earlier (*)  describes an object representing
events of a trace.  These objects contain pointers to other objects
representing other events of a trace.  Using the pointers, the
objects are arranged in a tree-like graph.  (It is not a true tree
because it contains cycles.)  See the Figure.

      Ignoring the "b" columns labeled "b1" and "b2", one can see
four rows of bars.  The top three are nested.  That is, excepting the
top bar each bar has a superior bar above it.  The bars in the second
and third rows, begin and end within their superior bar's left
(begin) and right (end) borders.  The bar in the bottom row differs
in that it overlaps the border of the bar above it.  In PieScope,
this bar would represent an asynchronous event.  The objects
representing these superior and inferior bars contain pointers to one
another.

      When PieScope draws the bars, it first checks the object
representing the most superior bars to determine whether they are to
be drawn.  Remember that these bars represent events and their edges
therefore represent timestamps.  PieScope checks these timestamps
before deciding to draw the bars.  If PieScope is looking at only
part of a trace, then it is possible that some bars will not be
drawn.  If no asynchronous events are present in a trace, then
PieScope knows that it does not need to look beneath a superior event
which it decides is not to be drawn.  Unfortunately, the current
algorithm does not provide PieScope with sufficient information for
it to know whether an asynchronous event lies under a superior event.

      With the current insertion algorithm, PieScope must examine an
entire trace each time it draws only a fractio...