The theme of this special issue reminds me of an article published by the 1973 Turing Award winner, Charles W. Bachman, in the Communications of the ACM, in November 1973, entitled: "The Programmer as Navigator." I remember the author saying: "I want to begin the programmer's training as a full-fledged navigator in an n-dimensional data space," and it made me picture the programmer flying through a 3D representation of the database schema. At the time it was just a dream, as the programmers of a CODASYL database had to work at the level of a sequential programming language to achieve their journey.
Still, this image of a programmer as a navigator serves to illustrate the point that the best way that human beings have found to master complexity is to build structures. Wherever structures are built, navigational facilities are required to move around within them. In the world of computers, structures are ubiquitous, and so is navigation. What varies from case to case is the means available for navigation.
In the use of computers, we can witness an irresistible evolution towards visual interfaces. It is therefore logical to see a similar evolution towards visual representation of structures, and visual navigation through these structures. For instance, most windowing systems nowadays include a file browser that displays the directory tree structure visually, allowing the user to display or hide individual subtrees. Localizing a file in such a tree structure is already a form of visual navigation, albeit rather simple.
Even command languages can include visual navigation features, even if they are often rather limited. For instance, many Unix shell languages include a file completion feature that allows the user to see what choices are available, given the partial file path typed so far. In such cases, the visual facility is rather limited and only available on demand. It is nevertheless a helpful feature for the users to navigate directory structures faster and more reliably. Indeed, the path selection process is less error-prone when the users can see, along the way to building the path, that they are on the right track, or notice, before they have finished typing, that they have mistyped earlier elements of the path.
There are many different structures for which visual navigation can be appropriate: file systems, data structures in programs, linking structures in a set of hypertext documents, visual specifications and programs, structured documents (SGML, HTML, XML), etc. The size of these structures can also vary dramatically, and one doesn't navigate in the same way through a structure having just a few dozen elements and a structure having hundreds of thousands of elements. One can nevertheless imagine that techniques used to visually navigate one kind of structure could potentially be useful to navigate another kind of structure. Similarities can be exploited and differences abstracted. For instance, similar techniques could be used to navigate a cross-reference graph showing procedure calls for a large scale application, and to navigate a Web site based on a site map.
Most of the examples mentioned above imply navigation in human-made structures. One exception is the navigation in a cross- reference graph. Indeed, such graphs are usually automatically built with information extracted from source code. The structure is derived from procedure declarations and procedure calls, which are rather simple to correlate. This approach of navigating a virtual structure that is completely automatically generated from some data/information set can be extended to the use of rather complex techniques that analyze the contents of the various elements and infer certain relationships that form a structure that can be represented and navigated visually.
For instance, hierarchical aglomerative clustering techniques (or other content-based clustering methods) can be used to group documents together based on similarities in their contents. These techniques require a similarity measure that is often implemented with artificial intelligence or statistical methods. A visual representation of the structure thus produced can then be used to locate components that are of interest to the user.
The paradigm of visual representation has an influence, nowadays, on a wide variety of domains: programming, program visualization, data visualization, user interfaces, hypertext and hypermedia visualization, interactive computing, browsing, general data exploration, etc.
The representation of complex structures in most of these domains requires that tools be built to dynamically display part of an overall structure, to allow the user to move around interactively within the structure, and to help the user grasp an understanding of each individual element of the structure as well as of the global structure so as to avoid user disorientation.
This special issue on visual navigation intends to focus on the approaches, methods and tools that have been or are being developed, based on a visual paradigm, to help the user navigate through complex software, data or information structures. The goal of this issue is to give a good overview of the state of the art in visual navigation in as wide a variety of domains as possible.
The article by Carriço et al. describes a method named "Integrated Multi-Views" that can display multiple areas of large graph-based diagrams while ensuring that edges connecting visible nodes remain visible, even when the nodes do not belong to the same viewing area. The system maintains the consistency between the various views, by ensuring that redundant and irrelevant information gets hidden.
The article by Chen describes the use of 3D and VRML representation of semantic structures similar to cognitive maps to help users find the documents they are looking for in a large collection of documents. The author shows how these visual semantic structures can provide landmark, route and survey information about the document collection to enable the user to navigate through these semantic structures. These structures are derived from proximity data calculated on the set of documents, taking into account user preferences.
The article by Gloor et al. bears some resemblance to Chen's article in that it also describes a tool that displays an overview map of a collection of documents, taking into account some knowledge about the intentions and goals of the user. Gloor's cybermaps are 2D representations based on automatic indexing and clustering techniques. Each element of a hyperdocument is represented as a node in the overview map and nodes are sequentially grouped/clustered into what the authors call hyperdrawers. The maps are visible while the users navigate through the hyperdocuments to help them see where they are and to show them the logical links that exist at their current location. The maps are updated dynamically and, based on users' profiles, a degree-of-interest function shows the nodes that are of higher interest to the user.
The article by Parker et al. describes a system that uses 3D visualization of large programs to help understand their structure. Programs are represented as nested graphs and rapid navigation techniques are provided to explore and understand the large information structures. These navigation facilities include rapid scaling and elision, as well as 3D widgets to control position, velocity and rotation along a vertical and a horizontal axis. The layout of the graphs can also be controlled, based on relationships between software components (inheritance, usage, etc.). The system also includes the possibility to visualize execution threads by showing virtual "snakes" move along the edges of the graphs.
These four articles will surely help you discover many interesting facets of visual navigation applied in a variety of contexts. They do not represent a complete overview of the domain, but nevertheless constitute a very interesting sample as many of the ideas presented can be abstracted from their specific context and re-applied in other contexts.
Bertrand Ibrahim is a tenured assistant professor at the University of Geneva since 1986 as well as student counsellor for the CS department since 1991. He graduated from the University of Geneva in 1977 with an M.Sc., then in 1982 with a Ph.D. in Computer Science. He then turned to computer-based learning and was active in a number of fields: networks, multilingualism, software engineering and visual programming. He has been an invited researcher at the University of California, Irvine, many times between 1985 and 1991. He leads a team of researchers funded by the Swiss National Science Foundation and his current research activities focus mostly on semi-formal visual languages, on software reuse based on natural language description of software artifacts, and on pedagogical uses of the WWW. He is actively involved in the WWW Virtual Library effort and maintains two entries, one on visual languages and visual programming, and the other on the Tcl/Tk scripting language.
Site Hosting: Bronco