Hierarchies, also know as tree structures, are collections of data
nodes where each node has a unique parent (node above it in the
hierarchy), but may have many siblings (nodes below it in the
hierarchy). In general, the nodes and the links between them can have
multiple attributes. The entire structure of the hierarchy and its
encompassing relations is also usually relevant. Tasks can be applied
to a single node, a link, a collection of nodes, or even to the entire
structure.
Hierarchical data is very diverse and is encountered in many forms.
Hierarchies naturally arise in taxonomies, the structures of
organizations, disk space management, genealogies, and the Dewey
Decimal system. Uses of hierarchies are almost as vast, including:
finding a particular node, viewing a node in the context of the entire
hierarchy, examining the over-all structure and relations of the tree,
and even finding duplicates or anomalies within the tree structure.
The traditional presentation of hierarchies usually consist of a 2-D
representation where child nodes are positioned under their parents in
wedge-like formations. Representing trees in this manner severly
limits both the depth and breadth of the tree that one can view at a
single time. Furthermore, navigating and finding specific nodes in
such a structure can be confusing, disorienting and downright
frustrating. More recent visualization techniques attempt to show
many more nodes, if not the entire tree itself, as well as providing
mechanisms for navigation and searching which allows the user to keep
the context of the entire tree in mind as well as reducing the
disorientation.
Hierarchies can be seen as a special case of networks, except the
definition of hierarchies eliminates the possibilities of dual paths
and cycles. Every
node in a hierarchy also has a unique path to the root node which is
not guaranteed to be the case with networks. Visualization of
hierarchies is related to 3-D data, as many visualizations use 3-D
graphics to render the results. Hierarchies are similiar to the
multi-dimensional data since the nodes in hierarchies usually contain a
fair number of attributes, but multi-dimensional data does not contain
the intrisic hierarchy in the data that hierarchical data usually
provides (e.g. folders and files on a disk).
The major players in the hierarchical visualization are Xerox PARC, with
their Cone Trees, and Hyperbolic Trees approachs, both of which have been
copied or used as a basis for many other projects. Treemaps, is
another significant representation in this genre, which was developed
in the HCIL at the University of Maryland.
Tasks
Obtain global relationships and structure from the entire hierarchy.
Find the most recent common ancestor between two nodes.
Find the path to a particular node from the root of the hierarchy.
Find clusters, duplicates, relationships, and inheritance
properties from the structure of the hierarchy.
Discovering attributes (especially the size) of nodes or entire subtrees.
Projects
CHEOPS. Centre
de recherche Informatique de Montréal. The Cheops approach maintains
context within a huge hierarchy, while
simultaneously providing easy access to details.
Visage. Maya design Group.
Visage provides an environment for exploring, analyzing, and visualizing
information.
WebTOC. HCIL - University of Maryland. By following local links,
WebTOC generates and displays a hierarchical representation of the
documents local to the site in the standard web-browsing environment.
Info Cube. Sony. This technique is based on the nested box metaphor and uses 3D
interactions.
TreeBrowser Abstract. HCIL - University of Maryland. Treeview is a
traditional hierarchy viewing object using a link-node
diagram.
TreeMap. HCIL - University of Maryland. Treemaps are a novel
visualization approach which completely utilizes the display as well as
being able to place over 5,000 nodes on the screen.
TreeViz. HCIL - University of Maryland.
TreeViz is a Macintosh implementation of the Treemap concept.
WebSpace. University of Minnesota. WebSpace is a program developed
to visualize the connections between HTML documents. Several types of display are
available.
Webviz.
Geometry Center - University of Minnesota. A web visualization
tool that views the web as a graph with the nodes being pages and the
links are represented as edges in the graph.
Docuverse.
Department of Information Science and Telecommunications - University
of Pittsburgh.
Docuverse represents a large document space in colored pie segments,
somewhat similiar to the structures of treemaps.
Webview.
Department of Information Science and Telecommunications - University
of Pittsburgh.
Related to Docuverse, Webview provides a tree-based structural display
of a smaller part of the file system
or document space.
Products
Hyperbolic
Tree. VizControls from Inxight (spinoff from Xerox - PARC). Displays
tree structures mapped to a hyperbolic space and which is visualized in
a fixed screen space.
Cone Trees. VizControls from Inxight (spinoff from Xerox - PARC).
Provides a 3-D representation and navigation of tree structures.
Winsurfer. HCIL - University of Maryland. Winsurfer is a Microsoft
Windows implementation of the treemaps concept.
HyperDir - Cygron. Visualizes your disk or directories in hyperbolic space.
(Microsoft Windows implementation).
Explorer
- Microsoft. Allows you to visualize your directories in a hierarchical
scrolling list.
Citations
Carriere, Jeremy and Kazman, Rick, Interacting with huge Hierarchies:
Beyond cone trees, Proc. IEEE Information Visualization '95, IEEE
Computer Press, Los Alamitos, CA (1995), 74-81.
This report
describes an augmentation of cone trees with graphical and interaction
technieques: usage-based filtering, animated zooming, hand-coupled
rotation, fish-eye zooming, coalescing of distant nodes, texturing,
effective use of color for depth cueing, and the applications of
dynamic queries. It also enhances the usefulness of cone tree
visualization for large hierarchies by all but eliminating clutter.
Johnson, Brian, and Shneiderman, Ben, Tree-maps: A space-filling
approach to the visualization of hierarchical information structures,
Proc. IEEE Visualization '91, IEEE, Piscataway, NJ (1991),
284-291.
This technique of hierarchical information allows 100%
utilization of the display space, while mapping the full hierarchy
onto a rectangular region. This efficient use of space allows large
hierarchies to be displayed in their entirety and facilitates the
presentation of semantic information.
The
essence of this scheme is to lay out the hierarchy in a uniform way on
a hyperbolic plane and map this plane onto a circular display region.
This approach makes components diminish is size as they move outwards,
and the display allows an exponential growth in the number of
components being viewed.
Asahi, T., and Shneiderman, B.,
Using treemaps to visualize the analytic hierarchy process,
Information Systems Research, 6, 4 (December 1995), 357-375.
Abstract: The Analytic Hierarchy Process (AHP), a
decision-making method based upon division of problem spaces into
hierarchies, is visualized
through the use of treemaps, which pack large amounts of hierarchical
information into small screen spaces. Two direct manipulation tools,
presented metaphorically as a "pump" and a "hook," were developed and
applied to the treemap to support AHP sensitivity analysis. The
problem of construction site selection is considered in this video.
Apart from its traditional use for problem/ information space
visualization,
the treemap also serves as a potent visual tool for "what if" type
analysis.
Chimera, R., Wolman, K., Mark, S., and Shneiderman, B. Evaluation of
three interfaces for browsing hierarchical tables of contents.
Technical Report CAR-TR-539, CS-TR-2620, University of Maryland,
College Park (February 1991).
Furnas, George W., Generalized fisheye views. In Proceedings of the
ACM SIGCHI Conference on Human Factors in Computing Systems,
ACM (April 1986), 16-23.
Feiner, R. Seeing the forest for the trees: Hierarchical display of
hypertext structures. In ACM Proc. COIS88 (Conf. on Office
Information Systems), Palo Alto, CA (March 1988), 205-212.
Jungmeister, W. A., Turo, D. (Nov. 1992)Adapting
treemaps to stock portfolio visualization, CS-TR-2996, CAR-TR-648,
SRC-TR-92-120.
Abstract: Treemap visualization techniques are extended and
applied to stock
market portfolios via a prototype application. Designed to facilitate
financial decision-making, the prototype provides an overview of large
amounts of hierarchical financial data and allows users to alter
aspects
of the visual display dynamically. Treemap concepts are illustrated via
examples which address common portfolio management needs.
Johnson, B., TreeViz: treemap visualization of hierarchically
structured information, In: CHI '92. Conference proceedings on Human
factors in computing systems, 369-370.
Koike, Hideki and Yoshihara, Hirotaka.
Fractal approaches for visualizing huge hierarchies. In
Proceedings of the 1993 IEEE Symposium on Visual Languages. IEEE
(1993).
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.
Lamping, John, Rao, Ramana, and Pirolli, Peter, A focus + context
technique based on hyperbolic geometry for visualizing large
hierarchies, Proc. of CHI'95.
Mitchell, Richard, Day, Davis, and Hirschman, Lynette, Fishing for
information on the internet, Proc. IEEE Information Visualization '95,
IEEE Computer Press, Los Alamitos, CA (1995), 105-111.
Mukherjea, Sougata, Foley, James D., and Hudson, Scott,
Visualizing complex hypermedia networks through multiple hierarchical
views, Proc. of ACM CHI '95 Conference: Human Factors in Computing
Systems, ACM, New York (1995), 331-337.
Abstract: Our work concerns visualizing the information space
of hypermedia systems using multiple hierarchical views. Although
overview
diagrams are useful for helping the user to navigate in a
hypermedia system, for any real-world system they become too
complicated
and large to be really useful. This is because these diagrams
represent complex network structures which are very difficult to
visualize and comprehend. On the other hand, effective
visualizations of hierarchies have been developed. Our strategy is to
provide
the user with different hierarchies, each giving a different
perspective to the underlying information space to help the user better
comprehend the information. We propose an algorithm based on
content and structural analysis to form hierarchies from hypermedia
networks. The algorithm is automatic but can be guided by the
user. The multiple hierarchies can be visualized in various ways. We
give examples of the implementation of the algorithm on two
hypermedia systems.
Nation, D.A., Plaisant, C., Marchionini, G., Komlodi, A. (May 1997)
Visualizing websites using a hierarchical table of contents
browser:WebTOC To appear in Proceedings of 3rd Conference on Human
Factors and the Web, Denver, Colorado (June 12), 1997. CS-TR-3791,
UMIACS-TR-97-41,CLIS-TR-97-08
Abstract: A method is described for visualizing the contents
of a Web site with a hierarchical table of contents using a Java
program and
applet called WebTOC. The automatically generated expand/contract
table of contents provides graphical information
indicating the number of elements in branches of the hierarchy as
well as individual and cumulative sizes. Color can be used to
represent another attribute such as file type and provide a rich
overview of the site for users and managers of the site. Early
results from user studies suggest that WebTOC is easily learned
and can assist users in navigating websites.
Robertson, George G., Card, Stuart K., and Mackinlay, Jock D.,
Information visualization using 3-D interactive animation,
Communications of the ACM 36, 4 (April 1993), 56-71.
Roberston, G.G., Mackinlay, J.D., and Card, S.K. Cone Trees: Animated
3D visualizations of hierarchical information, In Proceedings of
SIGCHI'91, (1991), 189-194.
Sarkar, M., Brown, M. Graphical Fisheye Views. Communications of the
ACM. 37, 12 (1994), 73-84.
Sarkar, Manojit,Snibbe, Scott, and Reiss, Steven . Stretching the
rubber sheet: A metaphor for visualizing large structure on small
screen. In Proceedings of the ACM Symposium on User Interface
Software and Technology. ACM Press (Nov 1993).
Shneiderman, B. Tree visualization with tree-maps: A 2-d space
filling approach.
ACM Transactions on Graphics. (1992).
Turo, D. (April 1994)
Hierarchical visualization with Treemaps: Making sense of pro
basketball data, Video in CHI '94 Video Program, ACM, New York. A
two page video summary also appears in ACM CHI '94 Conference
Companion, (Boston, MA, April 24-28, 1994), 441-442. Video also
available through HCIL as part of the 1993 HCIL Video Report.
Abstract: Treemaps support visualization of large
hierarchical information spaces. The treemap generation algorithm is
straightforward and
application prototypes have only minimal hardware requirements. Given
primary graphical encodings of area, color and enclosure, treemaps
are best suited for the tasks of outlier detection, cause-effect
analysis and location of specific nodesósatisfying user-specified
criteriaóin
their hierarchical context. Distortion effects extend treemap
capabilities by emphasizing node relationships in the diagram.
Vicente, K.J., Hayes, B.C., and Williges, R.C., Assaying and isolating
individual differences in searching a hierarchical file system. Human
Factors. 29(3) (1987), 349-359.