Proceedings of the workshop "Intelligent Educational Systems on the World Wide Web",
8th World Conference of the AIED Society, Kobe, Japan, 18-22 August 1997

Guided Navigation Through Hyperspace

Jim E. Greer and Tim Philip
ARIES Laboratory
University of Saskatchewan
Saskatoon, SK CANADA S7N 0W0


Hypermedia systems, and the World Wide Web (WWW) in particular, are growing at a staggering rate. Growing much more slowly is the availability of tools to assist users, especially novices, in navigating this huge information space. The phenomenon of becoming "lost in hyperspace" has been well documented in past years (Conklin, 1987; Thuring et al., 1995). Novice users experience problems with information overload as well as problems knowing where they are within hyperspace due to their lack of familiarity with hyperlinked structures. This research presents an abstraction on the concept of Trails to provide navigation support for novice users.

Trails are among the oldest conceptual aids for assisting navigation known to mankind. The idea of using Trails for navigation was incorporated in the first description of hypertext systems (Bush, 1945). In our work, the concept of Trails is approached from several different angles. We have developed tools that enable users to make use of Trails and reduce navigational difficulties.

In recent research, some forms of Tours have been designed for the WWW or other hypermedia systems (Nicol et al., 1995; Nielson, 1995). These are very often simple lists of WWW locations that users can visit in sequence. While providing useful coverage of a topic, these systems put the user into a passive mode and do nothing to support the development of hypermedia navigational skills. These are not so much tools for the user, rather these are tools for the plagued WebMaster who wants to keep users at bay. The hypermedia element has been removed.

On the other hand, adaptive hypermedia approaches (Brusilovsky, 1996) can provide guidance for navigational support. Global guidance requires that the user have a particular goal and motivation in mind. Local guidance, on the other hand, suggests the most relevant links for the user to follow from the current node. In this latter case, there may be no global goal and decisions are made by consulting information on the preferences, knowledge, and background of the user.

Several research projects have investigated local guidance. SHIVA uses a semantic network to describe the domain of the subject and make browsing recommendations (Zeiliger, 1993). Lai et al. (1995) present a system with multiple navigational tools where a Guider is added to the browser. This Guider keeps track of where the user has been. Each page of their WWW system has a special [PREREAD] tag which lists the locations that should be visited before the current one. If the user comes to a location with PREREAD identifiers that have not yet been seen, Guider notifies the student and suggests that the student read these prerequisite pages first. A graph of these nodes with preread tags as directed links forms a prerequisite graph.

In our approach, we attempt to integrate various forms of local guidance by providing a suite of tools to support the development of Web document collections, Web browsing trails, and tours.

Collections, Trails and Tours

Our work distinguishes between resource Collections, navigational HyperTrails, and linearized HyperTours. In (Philip, 1997) we formally define each of these notions but for this workshop we can informally define them as follows:

A Collection is a set of WWW resources, represented as a directed graph where each vertex is a tuple defined as <URL, MIMETYPE> and each edge is a tuple defined as <SOURCE_URL, DEST_URL, LINKTYPE>. Many link types are possible including topic, concept, prerequisite, crosslink, analogy, abstraction, or untyped. If no semantic information about links is available, all links in a collection are considered to be untyped. In systems like the MicroWeb Toolkit (Thomson et al., 1996), various link types can be attributed to links. A Collection is, thus, a subset of the WWW with a bit of additional type information.

A HyperTrail is an overlay on a Collection, typically used to represent a user's travels. In a normal WWW browsing scenario, a user is generating a HyperTrail on the Collection corresponding to the entire WWW. In our research, users generate HyperTrails on MicroWeb Collections (Thomson et al., 1996). A HyperTrail has two distinct elements that differ from a Collection. First, there is a temporal order to the elements of the HyperTrail. Each node except the root is temporally preceded by a specific node, and temporally followed by a specific node. This precedence information is stored in timestamps. Second, nodes can be visited more than once, with the impact that a single node may occur multiple times in a HyperTrail and a link may be duplicated several times with different timestamps. A HyperTrail ignores links that appear to be "back" operations and focuses instead on the minimum structure of the area visited. Thus nodes that are immediately revisited are considered to be branching nodes in a tree. Note that by ignoring any instances of links that return to a predecessor, the HyperTrail becomes a spanning tree and contains the visited nodes and the traversed links in a collection.

A HyperTour is a linearized form of a part of a HyperTrail. Simply stated, it is an ordered list of URLs. A HyperTour is usually created from a HyperTrail and thus the two are closely related. The distinction between a HyperTrail and a HyperTour is that a user creates a HyperTrail by browsing, whereas a user follows a HyperTour while browsing. It is important to distinguish between these two entities because while a user is taking a HyperTour, the user is also building a HyperTrail.

Next we present three different classes of HyperTours through a hypermedia resource Collection and describe tools that enable the generation of each.

Hand-Crafted HyperTours

In true form to Vannevar Bush's vision of the Memex system, user tools must be made available to allow users to create their own Trails through a hypermedia system (Bush, 1945). Users need the ability to connect two or more documents together that they themselves associate, and to add annotations to record their own thoughts. The minimum requirements for a tool based on Bush's Memex system are:

A well-designed browser should be built with these requirements in mind. We have developed a system which acts as a set of components to add Memex-like functionality to the Netscape Web browser. This system has been dubbed the Trail Blazer. The Trail Blazer hides in the background while users navigate, keeping a complete list of everywhere they have been. The user may add annotations to interesting locations, or to remove uninteresting locations from the Trail. When the user is finished browsing, he or she may save this information into a HyperTrail file for future reference or to share it with others.

The HyperTrails generated from a user's browsing can be edited into a hand-crafted HyperTour. The HyperTour takes as a default tour the sequence of nodes visited by the user as the HyperTrail was blazed. The HyperTour can be rearranged and edited to suit the desires of the user. Thus a customized tour of a set of Web resources can be built with little effort. Slightly more effort is required to edit the HyperTour or to add annotations or customized links between items in the HyperTrail.

Algorithmic HyperTours

The simplest from of a Tour on the WWW is a list of URLs, such as a bookmark list. Many recent implementations of Trails take this approach (Nicol et al., 1995). Trails can be constructed to direct users from place to place and show them through a particular set of information, similar to a tour in a museum. Such systems are very simple but have the drawback of not providing facilities for development of users' navigational skills. However, it is possible to provide the user with an opportunity to develop their navigational skills by adding simple features into such a system. For instance, the Footsteps system allows the user to browse outward from any given location in the tour (Nicol et al., 1995). At any time, the user may return to the last tour node to explore the local area further, or to progress in the tour. Although these are "static" tours, they still permit the user to engage in local unguided exploration which ideally leads to the development of independent navigational skills.

We have developed tools for the generation of algorithmic HyperTours based on the hyperlink structure of the WWW as viewed from a customized collection of WWW documents. Navigational techniques are algorithmically represented based upon the availability of explicit information about the interconnection of WWW resources. When users begin to look at a new WWW subset they can consider the available algorithmic HyperTours and pick an appropriate navigational plan (algorithm). Since each algorithm can be applied to any WWW subset, the user can see how the navigation technique works in different collections of WWW resources. Thus, the algorithmic HyperTours can be used as a medium for exploring navigational techniques.

For example, a particular algorithm could describe exhaustive coverage of a concept by taking a depth-first tour within subtopics, where subtopics are explored subject to prerequisite links. Thus, given a Collection or a HyperTrail as a starting point, this algorithm would consider all items related to a particular concept, would sequence the topics and subtopics to satisfy prerequisite constraints, and would visit items in a depth first fashion.

Several such algorithmic HyperTours are possible, ranging from overview tours to deep exhaustive tours.

Dynamic HyperTours

One of the problems that contributes to the "lost in hyperspace" phenomena is that of information overload (Nielson et al., 1995). A novice user reaches a location and becomes confused about where to go next. This is often caused by hypermedia pages with large numbers of (unorganized) hyperlinks and novice users who may lack the skills to make a sound navigational decision.

The WWW (or a MicroWeb Collection) is much like a Museum or a National Park. There are many sites available, but one does not find them by wandering aimlessly in a vague hope that one will stumble upon something wondrous. Instead, visitors follow well laid out trails or tours that take them from one natural wonder to another, or one could check with a "Guide" to see what is available. The Trail Guide in a park will typically take a surreptitious look at the tourist's shoes and recommend a tour that the tourist will be able to follow. Obviously, someone in dress shoes is not going to be interested in a 10km hike. By following a recommended tour and reading the guide information, one will learn about the wonders of the park.

We are working on the development of a decision support system, called the TourGuide, to help novice users make decisions about navigational choices. When novice users reach an impasse and cannot make a decision, they may ask the TourGuide to help them decide where to go next. In a similar manner to the tour guide in a park, our TourGuide will query the User Model (look at the shoes) and may recommend a pre-constructed tour or suggest an individualized tour.

The TourGuide is designed to take into account a user's current browsing activity, the information it knows about the individual user, and the information it knows about the hypermedia collection to make a suggestion about where to go next. The user may at any time resume normal navigation, making navigational decisions themselves, or continuing to ask the TourGuide for information on where to go. In this way novice users are supported as they search for relevant information yet are free to make their own navigational decisions when they wish.

When the Next button is hit, the system runs an algorithm, which is yet to be designed in detail but will hopefully function in the following manner:


The goals of this facet of the research are to put in place the support needed to perform this analysis and to implement a few different selection techniques. For instance, a simple selection technique could be to proceed from the current node in a depth-first fashion. If the user continuously hits the Next button, they would perform a depth-first traversal of the entire collection. Similarly, a breadth-first traversal could be used. More comprehensive techniques may consider the number of pages a user has looked at under each topic and determine which topics/concepts the user may wish to look into further and guide the user to these.

One goal of the research developed here is to design tools in such a way that they can take advantage of other systems. The formalization of HyperTrails into standard grammar/graph representation to take advantage of traditional algorithms is one example. The way in which algorithmic tours are generated from HyperTrails through the application of a decision function is another example. Using a similar process, it would be possible to take a planning/curriculum design system such as Peachy and McCalla's instructional planner (Peachy and McCalla, 1986) and connect it to the TourGuide. The student model needed in the Peachy and McCalla planner is readily compiled by tracking browsing behaviour. The domain model required by the planner can be mapped directly to that of a MicroWeb Collection. The Planner has been designed to pick a Tour through the Collection given the user model and domain knowledge base. The Executor is the TourGuide. It initially asks the Planner for a Tour, and present this Tour to the user. If the user ever deviates from that Tour, the Trail Guide would notify the Planner and ask for a new Tour. The Peachy and McCalla instructional planner becomes a real-time decision function for the Trail Guide in the same manner that decision functions are implemented for the creation of algorithmic Tours.

Using similar methods, other planning, curriculum design, or decision navigation systems may be integrated with this architecture.


The system resulting from this research is made up of three main components. The first is the Trail Blazer which allows users, as well as designers and maintainers, to create HyperTrails. The second component is the Tour Editor, which converts Trails to Tours and allows designers to create hand-crafted or algorithmic tours. The third component is the MicroWeb TourGuide, which provides users with additional guidance during browsing or while on a tour.

This research is aimed at exploring navigation assistance tools through the use of HyperTrails. This is done from three approaches. The first is to give users the ability to create their own HyperTrail, to access browsed material later, or to share it with others. Second, these HyperTrails may be presented to other (novice) users as HyperTours over a given Collection. Third, with the addition of specialized link types in a Collection, we believe that some level of automatic navigation support can be achieved.


Brusilovsky, P. (1996). Methods and Techniques of Adaptive Hypermedia. Journal of User Modeling and User Adapted Interaction, 6, 87-129.

Bush, V. (1945). As We May Think. The Atlantic Monthly, 101-108.

Conklin, J. (1987). A survey of Hypertext. IEEE Computer, 20, 17-41.

Eklund, J. (1995). Cognitive Models for structuring hypermedia and implications for learning from the world-wide web. Proceedings of the First Australian World Wide Web Conference.

Lai, M., Chen, B., & Yuan, S. (1995). Toward a new educational environment. Conference Proceedings, Fourth International World Wide Web Conference, 221-230.

Nicol, D., Smeaton, C., & Slater, A. (1995). Footsteps: Trail-blazing the Web. Proceedings of the 3rd International Conference on the World Wide Web. Darmstadt, Germany.

Nielson, J. (1995). Multimedia and Hypertext: The Internet and Beyond. Boston, MA: Academic Press Inc.

Peachy, D., & McCalla G. (1986). Using planning techniques in intelligent tutoring systems. In International Journal of Man-Machine Studies, 24, 77-98.

Philip, T. (1997). Blazing Trails and Guiding Learners on the WWW. Msc. Thesis Proposal, Department of Computer Science, University ofSaskatchewan.

Thomson, J., Cooke, J., & Greer, J. (1996). The MicroWeb Toolkit- Bringing the World Wide Web to the Classroom. In H. Maurer (Ed.), Proceedings of Webnet 96, SanFrancisco, AACE, 445-450.

Thuring, M., Hannemann, J., Haake, J. (1995). Hypermedia and Cognition: Designing for Comprehension. Communications of the ACM, 38(8), 57-66.

Zeiliger, R. (1993). Adaptive Testing: Contribution of the Shiva Model. In D. Leclercq and J. Bruno (Eds.): Item Banking: Interactive Testing and Self-Assessment. Nato ASI Series F, Vol. 112, Springer-Verlag, Berlin, 54-65.