Transcript Operating Systems Overview

Information Visualization and
Its Applications
信息可视化及其应用
Mao Lin Huang (黃茂林)
University of Technology, Sydney,
Visualization
(可视化)
Scientific Visualization
(科学计算可视化)
None Graph Visualization
(非图论型可视化)
Information Visualization
(信息可视化)
Graph Visualization
(图论型可视化)
Graph G = (V, E)
2
Information Visualization
Advances in science &
technology have allowed
people to see old things in new
ways. Telescopes, microscopes
and oscilloscopes are typical
instrument examples.
现代科学技术允许人们用新
的方法来看旧的事物. 例如
天文望远镜, 显微镜 ….
Maps, diagrams, and PERT charts
are examples of using visual
representations to see things. A
good picture is worth ten thousand
words.
一个好的图画所能表达的东西胜
过十万个字
Today, computers help people to
see and understand abstract data
through pictures.
3
The Definition (定义)
Information visualization: the use of interactive visual
representations of abstract, non-physically based data to
amplify cognition [CMS99].
信息可视化:
用可交流的, 视觉表达方式来表达抽象的, 非物理的
数据从而增强对数据的认识.
[CMS99]
Stuart K. Card, Jock D. Mackinlay, and Ben Shneiderman.
Readings in information visualization: using vision to think.
Morgan Kaufmann Publishers, Inc., 1999.
Xerox Palo Alto Research Center (PARC)
4
Information Visualization
None-relational data & Relational data
Graphics-driven & Graph-driven
The little image dots represent data records of the number of
sun spots, from 1850 to 1993, zoomed in on a small area.
(collected from GVU Center, Georgia I. T.)
An example of using SeeNet to view email data
volumes generated by AT&T long distance
network traffic. Edges represent email
connections. Weigh and colors of edges represent
volumes of email data.
5
Graph-DrivenGraph
Visualization
of Relational Data
Visualization
An example of
visualizing relational
data. This is the
visualization of a
family tree (graph).
Here each image
node represents a
person and the edges
represent
relationships among
these people in a
large family.
6
The Model of the Relational Data
关联数据模型
Relational information (graph) visualization systems use
graphs G = (V, E) to model relational structures: the entities
are nodes, and the relationships are edges (sometimes called
links).
For example, the structure of the World Wide Web can be
modeled as a graph: the nodes are HTML documents, and a
hyperlink from one document to another is represented as a
directed edge.
7
Challenges in GV




Graph layout Problem
Scale Problem
Scope Problem
Navigation Problem
Readability, cognitive effort
comprehension
Small window, large data sets
Context display
Distributed huge data sets,
which are partially unknown
How to find particular data
items by visual manipulation?
8
Classical Graph Layouts






Link-node diagrams
Layout algorithms (graph drawing)
Geometric positioning of nodes &
edges
Small amount of nodes
Avoid node overlaps
Reduce edge crossings
radial layout
symmetric
hierarchical
force-directed
orthogonal
9
The Graph Drawing (画图)
A drawing D(G) of a graph
G = (V, E) consists of a
location (x, y) for each v in V
and a route ((x1,y1), (x2, y2))
for each edge e in E.
一个“图画”是一个“图”
的几何表达方式.
A graph drawn using the
original spring algorithm.
一个用弾璜算法来画的图.
10
Classical Tree Layouts





A special type of graphs
With no circles
Structured hierarchically
Inefficient use of display space
Small amount of nodes
radial layout
radial layout
Classical hierarchical layout
balloon layout
hyperbolic tree
11
Space-Optimized Tree Layout
(We introduced this new method in 2001)





Redefine the wedge (v)
Efficient use of display space
Connection+enclosure
Large amount of nodes
How to navigate? (Distortion, Zooming+Filtering
context+detail)
A large data set of approximately 50 000 nodes
My Unix root with approx. 3700 directories and files
12
Redefine the wedge(v) of radial drawings
-A region P() of a node is defined by the wedge wg(v) and one (or more) cutting
edges (boundaries) cut by other regions that cross the line l in wg(v).
-A wedge is defined as wg() = {, l, ()}, where  is the father of  and l is a
straight line going through  that determines two boundaries of P().
13
The Problem of Viewing Large Data
大型数据可视化的问题
Traditional graph visualization assumes that the whole graph can reasonably be
represented in a readable and understandable manner on the display medium.
•
•
•
•
Amount of information we want to visualize becomes larger
A small modern file system (say with a 2GB drive on a PC) there are
hundreds of nodes and links
Web graphs are much larger; even a small organization such as a
University has many thousands of web documents.
No techniques can visualize the complete World Wide Web.
Classical visualization methods tend to be inadequate.
14
Clustered Layout (nodes grouping)
Connection + Enclosure
15
Clustered Layout





High scalability
Dynamic viewing
Abridged context
Open & close clusters
Average readability
16
Force-Directed Clustering (DA-TU)
(we introduced this method in 2002 and it’s the first attempt of
using force-directed method to draw clustered graphs)







Multi-level clustering
Multiple spring forces
High scalability
Dynamic viewing
Abridged context
Open & close clusters
Good readability
17
Multi-Forces in Clustered Graphs
18
The Online Graph Model 在线图模型







Proposed in 1997
Scope problem
is well addressed
Scalability is
increased through
dynamic viewing
Lost overall context
Change frames
Animation preserves
“mental map”
Modified Spring Algorithm
19
Online Navigational Visualization
(Online Force-Directed Animated Visualization)
We proposed OFDAV
in 1997 that provides a
major departure from
traditional methods.
We visualise a tiny part
(a “frame” Fi ) of a
huge graph at time t.
We change from Fi to
Fi+1 by user
interaction.
20
Online Navigational Visualisation
在线导航型可视化
OFDAV provides a major departure from traditional methods. We
visualise a tiny part (a “frame” Fi ) of a huge graph at time t. We change
from Fi to Fi+1 by user interaction.
OFDAV does not
need to know the
whole graph, it does
not predefine the
geometry (the user
can navigate
logically), and it is
user-oriented.
21
Scope Problem is Addressed
Small local graph
We incrementally calculate and maintain a small local
visualization on-line. The graph is supplied to the system
by a series of requests for neighbourhoods of focus
nodes.
new focus node v
neighbourhood of v
Huge
graph
22
Online Graph Layout Problem
The specific criteria for online drawing:



The layout of logical frame must show the direction of the
exploration.
Reduce the overlaps among the local regions.
The sequence of drawing preserves the mental map.
The general criteria for graph drawing:


Reduce the edge crossings.
Avoid nodes overlaps
23
Spring model (弹鐄模型)
In the spring model, each node is replaced by a steel ring, and
edges are replaced by Hookes’s law springs (胡克定理). The rings
have a gravitational repulsion (反向万有引力定理) acting between
them, and we can find a drawing which minimizes the energy.
24
Modified Spring Algorithm (MSA)
In this frame, there are two focus nodes, x and y. The total force
on node v is:
f (v)  fxv 
g
uv
u{1,...,4, x , y}

h
uv
u{ x , y}
25
The layout of Fi must show the direction
of the exploration.
Spring model
Modified spring model
26
Application1:Visual Web browser





WebOFDAV - mapping
the entire Web,
Look at the whole of
WWW as one graph; a
huge and partially
unknown graph.
Maintain and display a
subset of this huge
graph incrementally.
Reduce mouse-click
rate
Maintain a 2D map &
history of navigation
27
The “lost in hyperspace” problem
迷失在超空间

Even in this small document, which could be read in
one hour, users experienced the ‘lost in hyperspace’
phenomenon as exemplified by the following user
comment: ‘ I soon realized that if I did not read
something when I stumbled across it, then I would
not be able to find it later.’ Of the respondents, 56%
agreed fully or partly with the statement, ‘When
reading the report, I was often confused about where
I was.’ [Nielson, 1990].
28
Visual Web Browser addresses the problem of
“lost in hyperspace” with a sense of “space”.


Graphic Web Browser addresses the fundamental problem of
“lost in hyperspace” by displaying a sequence of logical
visual frames with a graphic “history tail” to track the
user’s current location and keep records of his previous
locations in the huge information space.
The logical neighborhood of the focus nodes indicates the
current location of the user, and the tail of history indicates
the path of the past locations during the navigation.
29
Application2:
File Management
and Site Mapping
Mapping to a Unix root with approx.
3700 directories and files
An example of using Space-Optimized
Tree Visualization for a small web site
mapping (approximately 80 pages)
- viewing techniques needed
30
Application3: Web Reverse Engineering

HWIT (Human Web Interface Tool) is able to reuse
existing structures of web site by visualizing and modifying
the corresponding web graphs, and then re-generating a new
site by save the modified web graphs.
The layout of an existing structure of a web site
Enhancing the existing Web site by adding a sub-site
31
Application4: B2C e-Commerce

VOS (Visual Online Shop) can be used for online grocery shopping,
shopping cart model. It is applicable to any e-commerce shopping
application (dynamically navigate e-catalogs).
32
Application5:
Online Business
Process Management



WbIVC (Web-based
Interactive Visual Component)
is applied to a research
project management system
(RPMS) in universities.
A participant can review the
details of a specific process
element by clicking on the
corresponding rectangle, and
then selecting the “open a
process element” in the
popup menu.
A participant can also create
a new artifact (a Java
methods) to a research
project by opening a edit
window.
The output interface of the WbIVC in RPMS
The input interface of the WbIVC in RPMS
33
Application6:
Program Understanding
and Software Mining




JavaMiner is for non-linear
visual browsing of huge java
code for programming
understanding.
textual data mining
Visualize a variety of
relationships between terms in
Java code, e.g. HAS,
SUBCLASS, CALL and
INTERFACE relationships.
Text documents, the lexicon,
the neighborhood function
The input interface of the WbIVC in RPMS
34
Conclusion


The above talk gives an introduction to Information
Visualization and covers most of research works I have
done in this field.
In the future, I will remain doing research across these
three layers because I believe that to guarantee the
quality of the research, it needs theory but to assess the
value of the research, it needs applications.
Thank You !
35