ACM Computing Surveys 31(4), December 1999, http://www.acm.org/surveys/Formatting.html. Copyright © 1999 by the Association for Computing Machinery, Inc. See the permissions statement below.


Information Visualization for Hypermedia Systems

Sougata Mukherjea
C&C Research Labs, NEC USA,
110 Rio Robles, San Jose, Ca 95134, USA
Email: sougata@ccrl.sj.nec.com


Abstract: Information Visualization can make hypermedia systems more usable by presenting a site map to assist in navigation. In this paper we explain some of the difficulties in developing effective visualizations of hypermedia information spaces and highlight some of the key systems and techniques that have been developed to overcome the difficulties. Finally, we discuss some of the major challenges for the next generation of information visualization researchers.

Categories and Subject Descriptors: H.5.4 [Information Interfaces and Presentation]: Hypertext/Hypermedia - Navigation,User Issues

General Terms: Human factors

Additional Key Words and Phrases: Information Visualization, Focus+Context Views



1 Introduction

A major problem in hypermedia systems is being lost in hyperspace: because there are no restrictions on how users navigate through the information space, they can become disoriented while navigating. This problem was evident even in older hypertext systems [Nielsen 1990] and has been multiplied in the World-Wide Web [Pitkow 1996]. Overview diagrams or site maps that visualize the structure and contents of the underlying information space and let users see where they are, what other information is available and how to access it, appear to be a useful tool for orientation and navigation in hypermedia documents [Utting 1989]. Information visualization can convert large amounts of information into meaningful and interpretable visual representations. Indeed, it can be argued that information visualization is particularly important because it allows people to use perceptual rather than cognitive reasoning in carrying out tasks [Vincente 1990].

2 Present Status

Construction of effective overview diagrams for large hypermedia systems involves various difficulties. Since information visualization involves abstract information which does not have any inherent visual appearance, it is more challenging than scientific visualization.

The overview diagrams generally show the structure of the hypermedia information space as a node and link graph diagram, the most popular way of depicting networks. For any real-world hypermedia system these will be large, complicated graphs. Attractive layout of the graph generally involves many aesthetics like avoiding edge crossings, keeping edge lengths uniform and distributing nodes uniformly. In general, the optimization problems associated with these aesthetics are NP-hard [Johnson 1984]. Extensive research has been done in finding approximate solutions using heuristics and other strategies for graph layout [Di Battista 1993]. Unfortunately, none of these approaches can form aesthetic layouts of large graphs in real-time.

Even with the discovery of a good layout, fitting a large graph on a screen is very difficult. A popular approach for the visualization of abstract information is to use Focus+Context techniques. In this technique the information of interest to the user is shown in detail, smoothly integrated with other context information. By balancing local detail and global context, this technique can simultaneously display information at multiple levels of abstraction. The technique was introduced by Furnas while presenting the Fisheye views [Furnas 1986]. This technique is appropriate in various contexts. For example, a Focus+Context technique for visualizing WWW nodes (by showing the neighborhood of the node as well as paths from landmark nodes) was presented in [Mukherjea 1997]. The Focus+Context technique has also been used to develop visualizations for classical data organizations like linear data (perspective walls [Mackinlay 1991]), tabular information (table lens [Rao 1994]) and hierarchies (hyperbolic browsers [Lamping 1995]). However, these data organizations are less complicated than graphs. Although Fisheye views have been used to display large graphs [Sarkar 1994], the technique can produce comprehensible diagrams for graphs with a maximum of about 100 nodes.

Given the obvious difficulties in visualizing large hypermedia structures, an effective approach has been to use various techniques to simplify the information space before the visualizations. Several information exploration systems that integrate data simplification and visualization techniques for the WWW have been developed including Navigational View Builder [Mukherjea 1995], Harmony Internet Browser [Andrews 1995], Narcissus [Hendley 1995] and WebCutter [Maarek 1997]. Techniques that can be used for data simplification include:

  • Filtering: Instead of visualizing a large hypermedia information space, one can visualize a filtered space that is of interest to the user. Obviously, search engines are one of the best techniques for this purpose. Combining searching with visualization is useful when the result of the search is too large for the user to comprehend (by letting the user browse through the results) or too small (by showing the user other related information). For example, the WebQuery system [Carriere 1997] integrates various visualization techniques to show the results of a search query along with all linked pages to the pages in the original result set.

    Since graphs are one of the most complicated data structures, filtering can be also used to form simpler structures for the visualization. For example, [Botafogo 1992] presents a technique that uses structural analysis to form hierarchies from hypermedia network structures. The technique was extended in [Mukherjea 1995a]. Another technique for inducing hierarchies in the World-Wide Web is explained in [Durand 1998].

  • Abstraction: Another approach to simplify the information space is to aggregate similar information together to form a high-level structure for the visualization. Extracting usable structures from a large hypermedia system is also useful. Traditional information retrieval clustering techniques [van Rijsbergen 1979] as well as newer techniques developed for the WWW [Pirolli 1996], [Pitkow 1997] can be used for forming the abstractions. Visualization techniques for a collection of related pages have been developed. For example, WebBook [Card 1996] is a set of related Web pages that can be organized and manipulated in various ways in a 3D space. On the other hand, [Chen 1997] introduced the Generalized Similarity Analysis framework which integrates several structuring mechanisms for generating virtual hypertext link structures. These structures were used to develop virtual reality enabled spatial hypertext in [Chen 1998]. Abstracting one level higher, [Terveen 1998] presents a visualization technique for clan graphs (a graph that groups together sets of related sites). This technique uses a web site instead of a web page as the basic unit of interaction and analysis.
More details on 3D visualization techniques for the WWW is presented in [Benford 2000]. It should be noted, as emphasized in [Pirolli 1996], that the World-Wide Web consists of three elements: content, usage and topology (or structure). An effective visualization should enable the user to understand all these elements of the information space. Most of the previously mentioned systems focus on visualizing the structure or the content. On the other hand, Disk Trees and Time Tubes are techniques for Web Ecology and Evolution Visualization [Chi 1998].

3 Future Directions

Although various promising techniques for visualizing information has been proposed and several visualization systems for hypermedia has been developed, unfortunately no system or technique has been proved to be really useful by extensive usability studies. Although usability studies for visualization techniques are being reported (for example, [Schaffer 1996] presents another proof of the usefulness of Fisheye techniques), more such studies are needed. Moreover, formal definitions and theories of what constitutes a ``good'' visualization has to be developed. Furnas has been a pioneer in this area [Furnas 1997].

Most visualizations of hypermedia systems has been based on the node and link graph diagram metaphor. Another popular metaphor is the landscape metaphor which has been used to visualize hierarchies [Tesler 1992], text databases [Chalmers 1992] or a collection of Web pages [Robertson 1998]. Other metaphors include bullseye [Carriere 1997] and auditorium [Terveen 1998]. Based on the usability studies and theories of effective visualization, we need to discover other metaphors that are appropriate for navigation on the WWW and develop unique visualizations based on them. Newer techniques for filtering and abstraction that are suitable for the Web are also essential.

Another key challenge for information visualization researchers is to make their systems usable by common computer users. At present it requires a lot of expertise and effort to develop visualizations of information spaces. We need to develop information exploration systems that allow designers of Web sites to easily form visualizations of their information spaces. Systems like SGI's Iris Explorer which has made scientific visualization commercially viable, shows the usefulness of such systems. Vanish [Carriere 1996] and Visage [Roth 1996] were two of the first information visualization tools. More such systems need to be developed. The systems should provide a library of effective data simplification and visualization techniques and the designers should be able to integrate several techniques to form visualizations of the underlying space. A standard data exchange (preferably be based on XML [DeRose 2000], the emerging standard for data exchange on the World-Wide Web) should be used. This will also allow the integration of newer techniques as they are developed.

Hopefully, with the understanding of what constitutes a ``good'' visualization and the development of systems that enable the designers to develop effective overview diagrams of their WWW sites, information visualization will make Web surfing more enjoyable for the users by reducing the lost in hyperspace problem.

References

[Andrews 1995] Keith Andrews. "Visualizing Cyberspace: Information Visualization in the Harmony Internet Browser" in Proceedings of the 1995 Information Visualization Symposium, 97-104, 1995.

[Benford 2000] Steven D. Benford, Ian Taylor, David Brailsford, Boriana Koleva, Michael Craven, Michael Fraser, Gail T. Reynard and Chris M. Greenhalgh. "Three-dimensional Visualisation of the World Wide Web" in ACM Computing Surveys Symposium on Hypertext, 2000.

[Botafogo 1992] Rodrigo A. Botafogo, Ehud Rivlin, and Ben Shneiderman. "Structural Analysis of Hypertexts: Identifying Hierarchies and Useful Metrics" in ACM Transactions on Information Systems, 10(2), 142-180, 1992.

[Card 1996] Stuart K. Card, George G. Robertson, and William York. "The WebBook and the Web Forager: An Information Workspace for the World-Wide Web" in Proceedings of ACM SIGCHI '96, Vancouver, Canada, 111‚117, April 1996.

[Carriere 1996] Jeromy Carriere and Rick Kazman. "Rapid Prototyping of Information Visualizations using VANISH" in Proceedings of the 1996 Information Visualization Symposium, San Francisco, CA, 21-28, 1996.

[Carriere 1997] Jeromy Carriere and Rick Kazman. "Searching and Visualizing the Web through Connectivity" in Proceedings of the Sixth International World-Wide Web Conference, Santa Clara, CA, 701-711, April 1997.

[Chalmers 1992] Matthew Chalmers and Paul Chitson. "Bead: Explorations in Information Visualization" in Proceedings of ACM SIGIR '92, Copenhagen, Denmark, 330-337, June 1992.

[Chen 1997] Chaomei Chen. "Structuring and Visualizing the WWW by Generalised Similarity Analysis" in Proceedings of ACM Hypertext '97, Southampton, UK, 177-186, April 1997.

[Chen 1998] Chaomei Chen and Mary Czerwinski. "From Latent Semantics to Spatial Hypertext - An Integrated Approach" in Proceedings of ACM Hypertext '98, Pittsburgh, PA, 77-86, June 1998.

[Chi 1998] Ed H. Chi, James Pitkow, Jock D. Mackinlay, Peter Pirolli, Rich Gossweiler, and Stuart K. Card. "Visualizing the Evolution of Web Ecologies" in Proceedings of ACM SIGCHI '98, Los Angeles, CA, 400‚407, April 1998.

[DeRose 2000] Steven J. DeRose. "XML Linking" in ACM Computing Surveys, Symposium on Hypertext and Hypermedia, 2000.

[Di Battista 1993] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tolis. "Algorithms for Drawing Graphs: an Annotated Bibliography" in Computational Geometry: Theory and Applications, 4, 235-282, 1994.

[Durand 1998] David G. Durand and Paul Kahn. "MAPA: A System for Inducing and Visualizing Hierarchy in Websites" in Proceedings of ACM Hypertext '98, Pittsburgh, PA, 66-78, June 1998.

[Furnas 1986] George W. Furnas. "Generalized Fisheye Views" in Proceedings of ACM SIGCHI '86 Boston, MA, 16-23, April 1996.

[Furnas 1997] George W. Furnas. "Effective View Navigation" in Proceedings of ACM SIGCHI '97, Atlanta, Ga, 367-374, March 1997.

[Hendley 1995] Robert J. Hendley, Nicholas S. Drew, Andrew Wood, and Russell Beale. "Narcissus: Visualizing Information" in Proceedings of the 1995 Information Visualization Symposium, Atlanta, GA, 90-96, 1995.

[Johnson 1984] David S. Johnson. "The NP-Completeness Column: an Ongoing Guide" in Journal of Algorithms, 5(2), 147-160, 1984.

[Lamping 1995] John Lamping, Ramona Rao, and Peter Pirolli. "A Focus+Context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies" in Proceedings of ACM SIGCHI '95, Denver, CO, 401‚408, May 1995.

[Maarek 1997] Yoelle Maarek, Y. and Issy Ben Shaul. "WebCutter: A System for Dynamic and Tailorable Site Mapping" in Proceedings of the Sixth International World-Wide Web Conference, Santa Clara, CA, 713-722, April 1997.

[Mackinlay 1991] Jock D. Mackinlay, Stuart K. Card, and George G. Robertson. "Perspective Wall: Detail and Context Smoothly Integrated" in Proceedings of ACM SIGCHI '91, New Orleans, LA, 173-179, April 1991.

[Mukherjea 1995] Sougata Mukherjea and James Foley. "Visualizing the World-Wide Web with the Navigational View Builder" in Computer Networks and ISDN Systems. Special Issue on the Third International World-Wide Web Conference, Darmstadt, Germany 27(6), 1075-1087, April 1995.

[Mukherjea 1995a] Sougata Mukherjea, James Foley, and Scott Hudson. "Visualizing Complex Hypermedia Networks Through Multiple Hierarchical Views" in Proceedings of the ACM SIGCHI '95 Denver, CO, 331-337, May 1995.

[Mukherjea 1997] Sougata Mukherjea and Yoshinori Hara. "Focus+Context Views of World-Wide Web Nodes" in Proceedings of ACM Hypertext '97, Southampton, UK,187-196, April 1997.

[Nielsen 1990] Jacob Nielsen and Uffe LyngbĘk. "Two Field Studies of Hypermedia Usability" in Hypertext: State of the Art, Ray McAleese and Catherine Green (editors), papers presented at the Hypertext 2 conference, York, UK, 1989. Intellect Ltd., Oxford, 1990.

[Pirolli 1996] Peter Pirolli, James Pitkow, and Ramona Rao. "Silk from a Sow's Ear: Extracting Usable Structures from the Web" in Proceedings of ACM SIGCHI '96, Vancouver, Canada, 118-125, April 1996.

[Pitkow 1996] James E. Pitkow and Colleen M. Kehoe. "Emerging Trends in the WWW User Population" in Communications of the ACM (CACM), 39(6) 106-108, June 1996.

[Pitkow 1997] James Pitkow and Peter Pirolli. "Life, Death and Lawfulness on the Electronic Frontier" in Proceedings of ACM SIGCHI '97, Atlanta, Ga, 383-390, March 1997

[Rao 1994] Ramona Rao and Stuart K. Card. "The Table Lens: Merging Graphical and Symbolic Representations in an Interactive Focus+Context Visualization for Tabular Information" in Proceedings of ACM SIGCHI '94, Boston, MA, 318-322, April 1994.

[Robertson 1998] George G. Robertson, Mary Czerwinski, Kevin Larson, Daniel Robbins, David Thiel, and Maarten van Dantzich. "Data Mountain: Using Spatial Memory for Document Management" in Proceedings of ACM UIST `98, San Francisco, CA, 153-162, November 1998.

[Roth 1996] Steven F. Roth, Peter Lucas, Jeffrey A. Senn, Cristina C. Gomberg, Michael B. Burks, Philip J. Stroffolino, John A. Kolojejchick, and Carolyn Dunmire. "Visage: A User Interface Environment for Exploring Information" in Proceedings of the 1996 Information Visualization Symposium, San Francisco, CA, 3-12, 1996.

[Sarkar 1994] Manojit Sarkar and Marc H. Brown. "Graphical Fisheye Views" in Communications of the ACM (CACM), 37(12), 73-84, December 1994.

[Schaffer 1996] Doug Schaffer, Zhengping Zuo, Saul Greenberg, Lyn Bartram, John Dill, Shelli Dubs and Mark Roseman. "Navigating Hierarchically Clustered Networks through Fisheye and Full-Zoom Methods" in ACM Transaction on Computer-Human Interaction (TOCHI), 3(2),162-188, June 1996.

[Terveen 1998] Loren G. Terveen and William C. Hill. "Finding and Visualizing Inter-site Clan Graphs" in Proceedings of ACM SIGCHI '98, Los Angeles, CA, 448-455, April 1998.

[Tesler 1992] Joel D. Tesler and Steven L. Strasnick. The 3D File System Navigator. Technical report, Silicon Graphics, Inc., Mountain View, California, [Online: anonymous ftp from sgi.com in directory fsn], 1992.

[Utting 1989] K. Utting and Nicole Yankelovich. "Context and Orientation in Hypermedia Networks" in ACM Transactions on Office Information Systems (TOIS), 7(1), 58-84, 1989.

[van Rijsbergen 1979] C. J. "Keith" van Rijsbergen. Information Retrieval. Butterworth, 1979.

[Vincente 1990] K. J. Vincente and J. Rasmussen. "The Ecology of Human Machine Systems: II. Mediating `'Direct Perception' in Complex Domain" in Ecological Psychology 2, 207-249, 1990.


Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.