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
C&C Research Labs, NEC USA,
110 Rio Robles, San Jose, Ca 95134, USA
[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].
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:
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.[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 firstname.lastname@example.org.