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.


Where have you been from here?
Trails in Hypertext Systems

Siegfried Reich, Leslie Carr, David De Roure, and Wendy Hall
University of Southampton     Web: http://www.soton.ac.uk/
Multimedia Research Group     Web: http://mmrg.ecs.soton.ac.uk/
Highfield Lane, Southampton, SO17 1BJ, UK

Email: sr@ecs.soton.ac.uk, lac@ecs.soton.ac.uk, dder@ecs.soton.ac.uk, andwh@ecs.soton.ac.uk

Web: http://www.ecs.soton.ac.uk/~sr/, http://www.staff.ecs.soton.ac.uk/~lac/, http://www.staff.ecs.soton.ac.uk/~dder, http://www.staff.ecs.soton.ac.uk/~wh,


Abstract: People are confronted with ever growing amounts of information. This makes it increasingly difficult to navigate vast information spaces in order to find appropriate information. User trails provide a mechanism that allows people not only to better manage their personal information spaces but also to ask questions such as "where do other people go from here?", "what else should I read?" or "how did we come to that conclusion?". The fact that trails are built with information about the users' browsing paths and activities makes them well suited for collaborative applications where users with similar interests are to be matched.

Categories and Subject Descriptors: H.5.4 [Hypertext/Hypermedia]: Navigation; H.5.3 [Group and Organization Interfaces]: Web-based Interaction

General Terms: Hypertext, Collaboration, Social Navigation

Additional Key Words and Phrases: User trails, open hypermedia system, software agents



1 Introduction

Since the Greek hero Theseus found his way out of the maze by fastening a thread to the entrance and unwinding it on his way in, we are familiar with the concept of user trails as a means for navigating unknown territories.

In hypertext, guided tours and trails are part of the repertoire of concepts that can be used to assist users in navigating vast amounts of information (for an overview of navigating hypertexts see e.g. [Nielsen 1995]). As early as 1945, [Bush 1945] envisaged trails (or paths as they are called elsewhere [Shipman 1998], [Zellweger 1989]) in order to provide a mechanism for finding a user's personal information but also to allow these trails to be available to other users. Bush also envisaged a new profession, the trail blazers, "... those who find delight in the task of establishing useful trails through the enormous mass of the common record." [Bush 1945].

Both tours and trails are collections of hypertext objects (i.e. nodes), similar to lists of bookmarks [Keller 1997]. Tours usually support a hierarchical structure; trails on the other hand, typically constitute a specific path a user has chosen in exploring a set of nodes. Hence, backtracking could for instance form part of a trail whereas it would not be part of a tour (see [Bieber 1994] for a discussion of backtracking). Interestingly both concepts use associations between different pieces of information in order to provide the users with a sequential view of the information space. This is somehow at variance with the fundamental idea of hypertext, namely to support non-linear access to information.

2 Applications of Tours and Trails

Though at first sight similar, guided tours and user trails suggest themselves to different types of applications.

Tours are typically applied to scenarios where users are introduced to an unfamiliar subject [Bieber 1997a], [Marshall 1989], [Trigg 1988]. In particular, tours can help to guide novice users through a set of nodes. This has several implications. For instance, in most cases tours are authored by domain experts explicitly, e.g. by teachers for educational applications [Shipman 1998]. Furthermore, branching tours offer a choice of destinations. It is important that the system indicates to users if they get off the track [Shipman 1998], [Trigg 1988].

Like tours, trails are first-class structures that are imposed over a set of nodes and that can be named, edited or communicated to others. Unlike tours however, trails have an activity associated with the individual steps - the trail marks - that a user has taken. This could be as simple as "traversing" a link; it could be any activity applied to the node such as "printing it out" [Chalmers 1998], [Pikrakis 1998]; or it could even be a script that is executed during the traversal [Zellweger 1989].

Another fundamental difference between tours and trails lies in the fact that the latter ones are established by a set of users making their way almost incidentally through the information space. Hence, trails more resemble "beaten paths" than perfectly laid out walk ways.

This results in trails qualifying themselves for entirely different application areas. Trails allow users to ask questions such as "who else has been here?", "where do people go from here?" or also "how did we come to that conclusion?" [De Roure 1998], [Trigg 1988]. Therefore, this category of systems can be thought of as recommender systems [Resnick 1997] in that they support users in making their choices.

3 Issues and Research Questions

There a number of research issues related to trails in hypertext systems. In this section we will give an overview.

The first issue concerns the acquisition of trail information. Using trails results in defining the relevance of information, e.g. for navigation, from the point of view of a particular set of people rather than pre-defined categorisations [Chalmers 1998]. This is opposed to automatic resource discovery (see also Chakrabarti's paper in this special issue [Chakrabarti 2000]). A side effect of this is that by having people do the (subjective) ratings complex, heterogeneous multimedia data can be handled more easily [Chalmers 1998]. Furthermore, recording a trail should be possible with minimal user effort at the same time guaranteeing the user's privacy by allowing them to choose which trails to publish [Hill 1997].

Secondly, the more accurate the system's recommendation to the users needs to be, the more complex (and intelligent) the processing will be. Therefore, different paradigms such as software agents offer themselves for application in this domain [Carr 1998], [Pikrakis 1998].

Another issue related in particular to trails concerns the activity performed when creating a trail mark. Clearly, not only will the individual activities be different but they will also be related to each other. Rosenberg [Rosenberg 1996] proposes a framework consisting of three basic types - acteme, episode and session - which can be used for grouping the various activities to higher level entities. Issues that arise include the question when to end a trail or also, whether a user's backtracking should be recorded (it might be an explicit indication to others not to follow a particular path).

The issue of coherence leads us to the more general question of understanding hypertext documents and what role trails can play to assist this process. One's own trail through a hypertext will not always be of use to other people, especially in the absence of additional meta information that provides coherence to the reader [Marshall 1989]. However, if coherence is given, tours as well as trails can be considered a metaphor that supports the understanding of documents, in particular when combined with e.g. graphical overview maps [Thüring 1995]. This indicates that trail models should support a concept similar to composite nodes, e.g. individual "hops" that would compose a "trip" through a hypertext. Users could then view the various legs of their journey before actually following a particular (sub-)trail.

Finally, not only do hypertexts change over time but so do the users' trails. This might be due to changing interests, improved knowledge of a domain, etc. This implies however, that the importance of trails will change over time. Experience has shown that changes in results stemming from growth of the trailbase were found confusing [De Roure 2000]. As more trails are created, the statistical profile of the trailbase alters, and the results that a query returns will change. Possible approaches to address this issue include degrading the relevance of trails over time by using a resource based concept (see e.g. [Moreau 1997]); or, the use of a clustering algorithm to identify and track changing interests [Crabtree 1998]. By that the importance of trails can be weighed over time.

4 Conclusion

Guided tours and trails are powerful concepts for assisting users in navigating vast information spaces. While tours often serve the purpose of introducing a subject, trails offer themselves to more advanced applications. In particular, the fact that trails are built with information about the users' browsing paths and activities makes them well suited for collaborative applications where users with similar interests are to be matched. Given that privacy is provided, this will allow trail-blazers to not only recommend related nodes but also to suggest users with similar interests.

References

[Bieber 1994] Michael Bieber and J. Wan. "Backtracking in a Multiple-window Hypertext Environment" in Proceedings of the ACM European Conference on Hypermedia Technology (ECHT '94), Edinburgh, Scotland, 158-166, September 1994.

[Bieber 1997a] Michael Bieber, Fabio Vitali, Helen Ashman, V. Balasubramanian and Harri Oinas-Kukkonen. "Fourth Generation Hypermedia: Some Missing Links for the World Wide Web" in International Journal of Human Computer Studies, 47 (1), 31-65 [Online: http://www.hbuk.co.uk/ap/ijhcs/webusability/], July 1997.

[Bush 1945] Vannevar Bush. "As We May Think" in The Atlantic Monthly, 176(1),101-108, [Online: http://www.isg.sfu.ca/~duchier/misc/vbush/], July 1945.

[Carr 1998] Leslie A. Carr, Wendy Hall, and Steven Hitchcock. "Link Services or Link Agents?" in Proceedings of ACM Hypertext '98, Pittsburgh PA, 113-122, [Online: http://acm.org/pubs/citations/proceedings/hypertext/276627/p113-carr/], June 1998.

[Chakrabarti 2000] Soumen Chakrabarti. "Recent Results in Automatic Web Resource Discovery" in ACM Computing Surveys, Symposium on Hypertext and Hypermedia, 2000.

[Chalmers 1998] Matthew Chalmers, Kerry Rodden and Dominique Brodbeck. "The Order of Things: Activity-centered Information Access" in Proceedings of the Seventh International World Wide Web Conference, 359-367, 1998.

[Crabtree 1998] I. Barry Crabtree and Stuart J. Soltysiak. "Identifying and Tracking Changing Interests" in International Journal of Digital Libraries, 2(1), 38-53, 1998.

[De Roure 1998] David C. De Roure, Wendy Hall, Siegfried Reich, Aggelos Pikrakis, Gary J. Hill, and Mark A. Stairmand. "An Open Architecture for Supporting Collaboration on the Web" in Proccedings of IEEE Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET ICE) '98, 90-95, 1998.

[De Roure 2000] David C. De Roure, Wendy Hall, Siegfried Reich, Aggelos Pikrakis, Gary J. Hill, and Mark A. Stairmand. "Memoir: An Open Framework for Enhanced Navigation of Distributed Information" in Information Processing & Management, Accepted for publication, 2000.

[Hill 1997] Gary J. Hill, Gerard Hutchings, Roger James, Steven Loades, Jacque Hal», and Michael Hatzopulous. "Exploiting Serendipity Amongst Users to Provide Support for Hypertext Navigation" in Proceedings of ACM Hypertext '97, Southampton, UK, 212-213, [Online: http://acm.org/pubs/citations/proceedings/hypertext/267437/p212-hill/], April 1997.

[Keller 1997] Richard M. Keller, Shawn R. Wolfe, James R. Chen, Joshua L. Rabinowitz, and Nathalie Mathe. "A Bookmarking Service for Organizing and Sharing URLs" in Proceedings of the Sixth International World Wide Web Conference, 1997.

[Marshall 1989] Catherine C. Marshall and Peggy M. Irish. "Guided Tours and On-line Presentations: How Authors Make Existing Hypertext Intelligible for Readers" in Proceedings of ACM Hypertext '89, Pittsburgh, PA, 15-26, November 1989.

[Moreau 1997] Luc Moreau and Christien Queinnec. "Design and Semantics of Quantum: a Language to Control Resource Consumption in Distributed Computing" in Usenix Conference on Domain-Specific Languages (DSL'97), 183-197, 1997.

[Nielsen 1995] Jacob Nielsen. Multimedia and Hypertext. The Internet and Beyond. Academic Press Professional, Boston, 1995.

[Pikrakis 1998] Aggelos Pikrakis,Tilemahos Bitsikas, Stelios Sfakianakis, Mike Hatzopoulos, David C. De Roure, Wendy Hall, Siegfried Reich, Gary J. Hill, and Mark A. Stairmand. "Memoir - Software Agents for Finding Similar Users by Trails" in Proceedings of Practical Application of Intelligent Agents and Multi-Agents (PAAM) '98, 453-466, 1998.

[Resnick 1997] Paul Resnick and Hal Varian. "Recommender Systems" in Communications of the ACM (CACM), 40 (3), 56-58, March 1997.

[Rosenberg 1996] Jim Rosenberg. "The Structure of Hypertext Activity" in Proceedings of ACM Hypertext '96, Washington DC, 22-29, March 1996.

[Shipman 1998] Frank M. Shipman, Richard K. Furuta, Donald A. Brenner, Chung-Chi Chung, and Hao-wei Hsieh. "Using Paths in the Classroom: Experiences and Adaptations" in Proceedings of ACM Hypertext '98, Pittsburg, PA, 267-276, June 1998.

[Thüring 1995] Manfred Thüring, Jürg Hannemann, and Jürg M. Haake. "Hypermedia and Cognition: Designing for Comprehension" in Communications of the ACM (CACM), 38 (8), 57-66, August 1995.

[Trigg 1988] Randall H. Trigg. "Guided Tours and Tabletops: Tools for Communicating in a Hypertext Environment" in ACM Transactions on Office Information Systems (TOIS), 6 (4), 398-414, 1988.

[Zellweger 1989] Polle T. Zellweger. "Scripted Documents: A Hypermedia Path Mechanism" in Proceedings of ACM Hypertext '89, Pittsburgh, PA, 1-14, November 1989.


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.