Fractal Approaches for Visualizing Huge Hierarchies

Fractal Approaches for Visualizing Huge Hierarchies

Proceedings of the 1993 IEEE Symposium on Visual Languages, pp.55-60, IEEE/CS, 1993.

Hideki Koike, Hirotaka Yoshihara

Department of Communications and Systems
1-5-1, Chofugaoka
Chofu, Tokyo 182, Japan
Tel: +81-424-83-2161
koike@is.uec.ac.jp
hirotaka@qr.cas.uec.ac.jp

ABSTRACT

This paper describes fractal approaches to the problems which associate with visualizing huge hierarchies. The geometrical characteristic of a fractal, self-similarity, allows users to visually interact with a huge tree in the same manner at every level of the tree. The fractal dimension, a measure of complexity, makes it possible to control the total amount of displayed nodes. A prototype visualization system for UNIX directories is also shown.

KEYWORDS:

1. Introduction

Visualization systems for hierarchical structures, especially for huge (The term huge is used as hundreds/thousands of data.) data structures, have a potential usefulness. For example, the visualization of whole UNIX directories might help system administrators to maintain the file systems. Since administrators could recognize, through the visualization, local file systems of each computer and remote file systems mounted by using NFS (Network File System), they might avoid mistakes, such as deleting or moving files which are being referenced by other computers.

It is, however, meaningless to visualize such huge data with a current tree visualization framework. With an exponential explosion in size of a tree, when users focus on a node, they cannot see the minimum information, such as its parent, children, or siblings, in a scrollable window. Also, an increase of visual elements is detrimental to human's cognitive load as well as to the system's response time.

On the other hand, we had proposed a fractal-based method for information display control, fractal views[10]. As is described later, this method can be applied to tree structures, and can control the number of displayed nodes without relation to the shape of trees. In [10], we applied our method to program display, and showed its ability with comparison to generalized fisheye views[6].

This paper, by focusing on the visualization of huge hierarchical structures, describes how our fractal approaches reduce these problems. The next section describes previous work for visualizing hierarchies and their problems. Section 3 describes our fractal approaches. Section 4 shows a prototype system we have developed. Section 5 discusses the limitations of our framework and some hints on how to solve them. Section 6 is a conclusion.

2 Visualizing Huge Hierarchies

2.1 Exponential Explosion in Size

There exist many interactive visual systems which display hierarchical structures as trees on video displays[22,20]. In general, such systems use conventional tree layout algorithms[24,15,3], which lay out nodes as economically and attractively as possible based on the size of node and the offset between nodes. The width of the tree, however, increases exponentially corresponding to the depth of the tree. Consider, for example, an N branch tree in 2D (Figure 1).

Figure 1: Two-dimensional tree layout. dn is the width which is necessary to draw all subtrees under the tree at depth n. To simplify the problem, the offset is set to 0. Then, the width dn in depth n is represented as:

dn = N dn-1

To generalize:

dn = d1 N^(n-1)

It is clear that the width increases exponentially.

The ConeTree[16] developed at Xerox PARC demonstrated a 3D tree visualization framework. The ConeTree made it possible to display larger number of nodes by using 3D space. The exponential explosion in size, however, remains the same. Figure 2 represents the top view of a cone tree for an N branch tree. In this figure, rn is a radius which is necessary to draw all cones under the cone at depth n. It means that the radius of the cone at depth n is rn - rn-1. It is easy to note the following relation.

r(n-1)/(rn - r(n-1)) = sin θ/2

rn = {1 + 1/sin(pi/N)} r(n-1)

To generalize:

rn = r1 {1 + 1/ sin(pi/N)}^(n-1)

The tree size also increases exponentially.

Figure 2: The top view of a cone tree for an N branch tree. rn is the radius which is necessary to draw all cones under the cone at depth n.

2.2 Scrolling is Useless

The exponential explosion in size causes overflow off the screen. The general solution of this problem is scrolling. Scrolling is a technique to see, through a window which is physically limited in size, a object which is larger than the window size, by moving it horizontally or vertically. With scrolling, users can see the local details of every part of the tree.

In case of huge trees, however, the scrolling is no practical use. As the tree size increases exponentially, the distance between nodes also increases, especially at upper level of the tree. As a result, when the users focus on a node, they cannot see the minimum information such as its parent, children, or siblings in a scrollable window. Also, it is hard to trace links with scrolling to see its neighbors. When users reach another node, they cannot see the original node any more.

Thus, the combination of the conventional tree layout and the scrolling is not appropriate to the visualization framework for huge hierarchies.

2.3 Increase of Visual Elements

It should be also considered how the increase of visual elements affects users' cognitive load as well as the system's response time. It is often said that the human understands information faster and more clearly in visual representations than in text. Using the parallelism capability of human's visual and cognitive system, we are able to rapidly process many pieces of information at one time. The increase of visual elements, however, makes the diagram complex, and as a result it adversely affects our cognition.

Also, the increase of visual elements reduces the system's response time. In visual systems, the refresh rate of the graphics deteriorates with an increasing number of displayed objects. Visualization systems for huge data, therefore, should have the ability to reduce visual elements.

3 Fractal Approach

In the previous section, two problems are addressed for the visualization of huge hierarchies. In this section, we will describe our fractal approaches to these problems. Although the two approaches are based on a concept of a fractal, it is important to notice that each approach uses a different characteristic of a fractal.

3.1 Fractal Views

As is well known, a word fractal was proposed by B. Mandelbrot[12] and it represents a wide variety of self-similar objects. For example, a binary tree in Figure 3 is a fractal. Each edge length is r times larger than its previous one. There exists a relation:

D = - log r N

between the branching factor, N, and the scale factor, r. This constant D is called a fractal dimension.

Figure 3: A fractal tree.

Although general trees are not self-similar, if the relation:

D = - log rx Nx

exists between the branching factor Nx at node x and the scale factor rx, this tree is also said to be a fractal (The detailed discussion is held in [10]).

In [10], we had proposed a fractal-based method for information display control, fractal views, which is an extension of a fractal concept to logical trees. Fractal views calculate the degree of importance, which is called fractal value for convenience, of each node, and decide which nodes should be displayed or erased based on these fractal values. The fractal value Fvx of node x is calculated with the following equation.

Fv(focus) = 1
Fv(child_of_x) = rx Fvx
rx = C Nx^(-1/D)

where Nx is a branching factor at node x, D is a fractal dimension, and C is a constant value which satisfies 0 < C <= 1. For simplify the calculation, C is set to 1 in our system.

The most important property of fractal views is the ability to control the amount of data displayed. In an N branch tree, the total number of nodes, M, whose depth is smaller than or equal to n, is represented as:

M = {N^(n+1) - 1}/(N - 1)

On the other hand, the propagated value, Fv, of node at depth n is

Fv = r^n = N^(-n/D)

Thus, M is represented without n as:

M = {Fv^(-D) - 1/N}/(1 - 1/N)

As N becomes large, M moves asymptotically towards Fv^(-D). It should be noticed that M begins to approach Fv^(-D) at relatively small branching factor, N, of 3 or 4. That is, the number of nodes which have a value greater than or equal to the threshold is nearly constant without a relation to the branching factor.

There is a similar method called generalized fisheye views by Furnas[6]. In fisheye views, the degree of importance (DOI) of each node is calculated, with a distance from the root (-API) and a distance from the focus (D), as:

DOI = API - D

Since the number of nodes which have the same DOI value increases corresponding to the branching factor, it is hard to control the number of displayed nodes. Section 4.3 describes the comparative experiments with fisheye views and fractal views.

3.2 Fractal Tree Layout

Using the self-similarity characteristic of a fractal, it is possible to standardize the view at every level of the tree. In a fractal tree, a similar view is obtained when a subtree is magnified. When a part of the subtree is magnified, a similar view appears as well. Figure 4 represents this concept. However huge the displayed tree is, the view obtained by focusing on a part of the tree is almost the same. In a visualization system for hierarchical structures, nodes have more important roles than edges. Thus, each node size should be reduced with the edge length using the same scale factors.

Figure 4: The concept of fractal layout.

If we use this framework, we cannot recognize nodes whose sizes are smaller than a threshold. This is not shortcoming of our framework. On the contrary, users can concentrate their attention on the focus and its neighbors since they may not see the nodes far from the focus. Moreover, as is clear from the previous discussion, the number of nodes whose fractal values are greater than a threshold is nearly constant. In the fractal tree layout, each node size is proportional to its fractal value. Thus, the number of recognizable nodes is almost constant.

3.3 Fractal Pruning

Although the fractal layout makes it possible to keep the total amount of recognizable nodes to be nearly constant, it is not enough for a practical visualization system. Since all the displayed nodes, whether they are recognizable or not, reduce the system's response time, these unrecognizable nodes as well as the nodes outside the viewing area should be erased.

Fractal views can be used for this purpose. Following equation, the fractal value of each node is calculated. If we erase the nodes which have smaller values than a threshold, we can display the nodes near the focus. It is important that, once the threshold is set, the number of displayed nodes is constant when users change their focus of attention. It makes it possible to keep the system's response time to be constant, and it may also keep human's cognitive load to be constant.

4 Prototype System

4.1 Overview

A visualization system (This system was implemented in our software visualization system VOGUE[8,9].) for UNIX directories is implemented. Figure 5 is a snapshot of the screen. When the system is executed with a directory name, after the directory information is obtained by using UNIX system calls, a 3D tree whose root node represents the directory appears on the screen. The reason we adopted the 3D framework is to make effective use of the screen. Each node corresponds to the UNIX file, and its label represents its pathname. The color assigned to nodes represents file's type such as ASCII file, binary file, or directory. The relation between a parent directory and its subdirectory is represented as a link. Symbolic links in UNIX are represented as additional links with different color.

Figure 5: Snapshot of the screen.

The system supplies several interaction capabilities. Four vertical sliders are used to change users' viewpoints with animation. Although how to change viewpoints in 3D is an important problem to be solved, it is beyond of our research. Thus, some ways to move in 3D space were prepared. There are also several buttons on the control panel. For demonstrational purpose, users can choose the tree layout from 2D, ConeTree, and Fractal Tree, by pushing the button on the panel. When users select a node corresponding to a text file by mouse and pushes the ``Edit'' button, an editor window will open. The ``Find'' button is used to find a specific file. Since there are huge numbers of nodes, it is sometimes hard to find visually the specific node. When users type a file name that they want to see, and push the button, a node with the name highlights. Also, there are the ``Fisheye'' button and the ``Fractal'' button. The details of these buttons are described later.

Self-similar Views

Figure 5 and Figure 6 show how a user moves his/her focus of attention. First, the user's focus is on the root node in Figure 5, and he/she can identify its children. When he/she selects one of the children and zooms in with a slider, the cone with the child and grandchildren, which is very similar to the cone with the root and its children, appears (see the upper figure in Figure 6. Also, when he/she selects one of the grandchildren and zooms in, another cone which is also similar to other cones, appears (see the lower figure in Figure 6). Throughout the whole tree, the user can see the local relation and can manipulate nodes in the same manner.

Through the experimental use of our system, we found that users need a smaller number of mouse actions in the fractal style than in the normal cone style. This is because the users can move their focus to a subdirectory in only one action with fractal style. On the other hand, with normal cone style, they have to use sliders to find children, especially at upper levels of the tree.

Figure 6: Examples of self-similar views.

Pruning

The system also has the capability to reduce visual elements with fisheye views or fractal views. If the user selects a node and pushes the ``Fisheye'' button on the control panel, the whole path from the selected node to the root node is displayed. If he/she increments the threshold by pushing on the button on the panel, the number of displayed nodes increases. The number of displayed nodes, however, changes considerably when the user increments (or decrements) the threshold, such as in Figure 7. It was also found that the number of displayed nodes changes considerably when the user changes his/her focus even if he/she set the same threshold. In our experiments, fisheye views were not effective to control the number of nodes, especially in a huge tree.

Figure 7: An example of fisheye views.

Figure 8: An example of fractal views.

Alternatively, when the user selects the ``Fractal'' button, he/she can obtain fractal views from the focus. Initially, fractal views do not display the whole path to the root. By changing a threshold with a slider, it is possible to increase the number of displayed nodes almost continuously, such as in Figure 8. %The reason we use the slider to change the threshold is that there are %more effective thresholds in fractal views than in fisheye views. When the user selects another node, the fractal view from the new focus is obtained interactively. Then, the number of displayed nodes is kept to be nearly constant even if the user focuses on any nodes. The combination of the fractal layout and the fractal pruning made it easier to browse huge trees such as UNIX directories.

5 Discussion

Our simple idea to apply a fractal to the tree layout made it possible to visually interact with a huge tree in the same manner at every level of the tree. This is due to the fractal's geometrical characteristic, self-similarity. It is important that the number of recognizable nodes is almost constant in this framework. Users can see almost the same number of nodes.

It should be noticed that the information display control we presented here is not based on this self-similarity. It uses the fractal dimension which is a measure of complexity. It is assured that fractal objects created by the same dimension have the same complexity even if they have different shapes. Roughly speaking, fractal views replace the same complexity in physical objects with the same amount in logical trees. Since the displayed nodes are kept to be nearly constant in fractal views, both users' cognitive load and system's response time are kept to be nearly constant.

On the other hand, many problems remain unsolved. First, strictly speaking, our framework is not a 3D layout algorithm, because currently our algorithm does not check the overlap of cones. In our framework, each edge length is decided in a topdown manner. Therefore, it is not possible to change the edge length for preventing overlapping.

This problem is partially solved by changing a fractal dimension, D. In case of a 2D fractal tree, the fractal dimension represents the dimension of a set of branch tips. If the fractal dimension becomes smaller, the space between tips becomes larger. Thus, if we use a smaller dimension, the overlap of cones could be minimized.

Another factor to prevent overlapping is the concept of self-avoidance[12, page 152]. It is important to notice that, in fractal trees, self-similarity is different from self-avoidance. The angle of each branch has no relation to the fractal dimension D and the scale factor r. The angle is decided independently. Figure 9 is a fractal binary tree with the same fractal dimension of the tree in Figure 3, but it is prevented from overlapping of edges.

Figure 9: A fractal tree. Although its fractal dimension is the same as that of Figure 3, its edges do not overlap each other.

There are many capabilities to be embedded in our system. For example, automatic rotation of cones, which was demonstrated in the ConeTrees, is useful. Shadows[16,7] of 3D objects may help users' cognition. Also, formal user studies have to be done.

6 Conclusion

In this paper, we proposed fractal approaches for visualization of huge hierarchies. The geometrical characteristic of a fractal, self-similarity, made it possible to visually interact with a huge tree in the same manner at every level of the tree. The fractal dimension, a measure of complexity, made it possible to keep the number of displayed nodes nearly constant. Although a tree visualization might seem to be an old-fashioned theme to research, many problems, however, remain unsolved.

Visual systems, such as visual programming systems[18], algorithm animation systems[21,3], and so on, have been found a great success in the last decade. They, however, have manipulated rather small amounts of data. We believe visual representations will play more crucial roles in visualizing huge data, due to their ability to abstract information. Thus, for further success of visual systems, it is important to identify the problems that happen in applying current visualization framework to huge data structures.

Reference

  1. M. H. Brown. Algorithm Animation. MIT Press, Cambridge, MA, 1988.
  2. M. H. Brown. Zeus: A system for algorithm animation and multi-view editing. In 1991 IEEE Workshop on Visual Languages, pp.4-9, October 1991.
  3. P. Eades and R. Tamassia. Algorithms for automatic graph drawing: An annotated bibliography. Technical Report 82, Dept. of Computer Science, Univ. of Queensland, 1987.
  4. K. M. Fairchild, S. E. Poltrock, and G. W. Furnas. SemNet: Three-Dimensional Graphic Representation of Large Knowledge Bases. In R. Guindon, editor, Cognitive Science And Its Applications For Human-Computer Interaction, pp. 201-233. Lawrence Erlbaum Associates, 1988.
  5. J. Feder. FRACTALS. Plenum, New York, 1988.
  6. G. W. Furnas. Generalized fisheye views. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI'86), pp.16-23. ACM Press, 1986.
  7. K. P. Herndon, R. C. Zeleznik, D. C. Robbins, D. B. Conner, S. S. Snibbe, and A. van Dam. Interactive Shadows. In Proceedings of the ACM Symposium on User Interface Software and Technology (UIST'92), pp. 1-6, 1992.
  8. H. Koike. An application of three-dimensional visualization to object-oriented programming. In T. Catarci, M. F. Costabile, and S. Levialdi, editors, Advanced Visual Interfaces (Proceedings of the International Workshop AVI'92), pp.180-192. World Scientific, 1992.
  9. H. Koike. The Role of Another Spatial Dimension in Software Visualization. ACM Transaction on Information Systems, Vol. 11, No. 3,, July 1993.
  10. H. Koike and T. Ishii. A fractal-based method for information display control. Trans. of Information Processing Society of Japan, Vol. 33, No. 2, pp. 101-109, 1992.
  11. H. Lieberman. A Three-Dimensional Representation for Program Execution. In Proceedings of 1989 IEEE Workshop on Visual Languages. IEEE CS Press, 1989.
  12. B. B. Mandelbrot. The Fractal Geometry of Nature. W.H.Freeman and Company, New York, 1982.
  13. H.-O. Peitgen, H. Jurgens, and D. Saupe, editors. Fractals for the Classroom: Part One Introduction to Fractals and Chaos. Springer-Verlag, New York, 1992.
  14. H.-O. Peitgen and D. Saupe, editors. The Science of Fractal Images. Springer-Verlag, 1988.
  15. E. M. Reingold and J. S. Tilford. Tidier drawings of trees. IEEE Trans. on Software Engineering, Vol. 7, No. 2, pp. 223-228, 1981.
  16. G. G. Robertson, J. D. Mackinlay, and S. K. Card. Cone Trees: Animated 3D Visualizations of Hierarchical Information. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI'91), pp. 189-194. ACM Press, 1991.
  17. M. Sarkar and M. H. Brown. Graphical fisheye views of graphs. In Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI'92), pp. 83-91. ACM Press, 1992.
  18. N. C. Shu. Visual Programming. Van Nostrand Reinhold, New York, 1988.
  19. Silicon Graphics, Inc. FSN: File System Navigator, 1992. online manual.
  20. Silicon Graphics, Inc. IRIS WorkSpace User's Guide, 1992.
  21. J. T. Stasko. TANGO: A Framework and System for Algorithm Animation. Computer, Vol. 23, No. 9, pp. 27-39, September 1990.
  22. W. Teitelman and L. Masinter. The Interlisp programming environment. In D. R. Barstow, H. E. Shrobe, and E. Sandewall, editors, Interactive Programming Environments. McGraw-Hill, 1984.
  23. T. Vicsek. Fractal Growth Phenomena. World Scientific, London, 1989.
  24. C. Wetherell and A. Shannon. Tidy drawings of trees. IEEE Trans. on Software Engineering, Vol. 5, No. 5, pp. 514-520, 1979.