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.


Dynamic Hypertext: Querying and Linking

Richard Bodner and Mark Chignell
University of Toronto     Web: http://www.utoronto.ca/
Interactive Media Laboratory     Web: http://www.imedia.mie.utoronto.ca/
5 King's College Road, Toronto, Ontario, Canada M5S 3G8
Email: rbodner@mie.utoronto.ca, chignell@mie.utoronto.ca
Web: http://www.imedia.mie.utoronto.ca/people/rbodner, http://www.imedia.mie.utoronto.ca/people/chignell

Abstract: There are many models of hypertext, distinguished by a number of factors such as the underlying semantic data model (link typing and node typing), the degree of dynamic linking in the hypertext, and how dynamism and other behaviours are implemented. This essay examines a particular approach to dynamism in hypertext, based on the degree of similarity between a text passage in a source node and the text of a target node. It reviews work carried out over the past decade in creating systems for markup-based querying and dynamic hypertext, with particular emphasis on a model of dynamic hypertext that computes hypertext links on the fly using queries.

Categories and Subject Descriptors: H.1.2 [Models and Principles]: User/Machine Systems-human information processing; H.3.3 [Information Storage and Retrieval] Information Search and Retrieval-retrieval models; H.5.4 [Information Interfaces and Presentation]: Hypertext/Hypermedia-navigation

General Terms: Information Interfaces, Information Systems

Additional Keywords and Phrases: Information retrieval interface, dynamic linking, hypertext browsing


Table of Contents



1. Introduction

The idea of linking documents and images to one another can be attributed to Bush [Bush 1945]. Bush envisioned a "memex" machine, which, among many other things, could assist the scientist in developing associative indexes or "trails" through a collection of documents. Essentially, Bush described a hypertext structuring mechanism. Bush viewed collections of links as forming trails through hypertext, or paths that expert trailblazers would build to help other readers.

Traditional approaches to hypertext assumed that authors created well-defined (pre-defined) paths or trails in hypertext. When the reader approached the hypertext, the trail was already available. In this approach, inter-node links changed only when an author either updated or deleted them. The role of the author was to create the hypertext and the role of the user/reader was to browse through it. Thus, the reader was faced with the task of understanding the author's mental model of the hypertext documents in order to navigate the collection of linked nodes (hyperbase) effectively. There was no opportunity for readers to personalize the hypertext according to their interests, or for the types of links that were available to be adapted to the particular situation or task.

In the remainder of this essay we discuss the implications of a more dynamic model of defining links in hypertext, situating it within a decade-long research program concerned with how innovative text markup interfaces can integrate the tasks of querying and browsing. Our definition of dynamic hypertext will focus primarily on the dynamism of links, with links being created on the fly, based on knowledge of the corpus and the interests of the user. In this approach user interests are inferred by recording the interactions (selections made) with the system.

2. Hypertext and Strong Authoring

Conklin describes the concept of hypertext as being "windows on the screen [that] are associated with objects in a database, and links are provided between these objects, both graphical (as labelled tokens) and in the database (as pointer)" [Conklin 1987a], p. 17 . In a completely static hypertext, links, once authored, do not change over time. However, in many contexts, links created for a "one size fits all" mode do not cater to the requirements of particular users or tasks.

Cooke and Williams [Cooke 1989] , and Baird and Percival [Baird 1989] stated that users should be able to freely explore a hypertext document and collection via multiple pathways instead of being confined to a fixed structure. This worthy goal is difficult to implement when links are pre-authored and fixed. No matter how many pathways are authored, it is impossible to implement all the possible pathways required by each individual user carrying out a specific task.

A "strong authoring" model of hypertext assumes that the author "knows best". Authors express their vision of relationships within and between texts (nodes), and readers must then discern this structure and respond appropriately when navigating the resulting hypertext. Not surprisingly, readers often have difficulties navigating authors' structures. In amongst all the possible node relationships, one has to follow the particular path set by the author, a path that may not always seem natural or obvious to the reader. This may lead to cognitive overload and disorientation -- or a sense of being "lost in hyperspace" (see [Conklin 1987], [Nielsen 1990] and [Parunak 1989]). However, the embedding of links within hierarchical structures (as is the case in many Web sites) and the use of orientation cues and maps makes such problems less likely to affect users. Navigational aids, such as maps and tables of contents primarily provide structural links, and the problems still remain for links embedded within the text of the node. Due to these deficiencies, a hypertext collection is often supplemented with some sort of search facility. The use of search facilities typically causes the reader to create a "spiky" navigation pattern (see [Campagnini 1989] and [Parunak 1989]) or a description). Due to this spiky pattern users navigate in two modes: searching (e.g., querying the system) and browsing (e.g., reviewing the documents retrieved based on the previous query). This can be a difficult process for many users, especially novices who tend to have difficulty expressing their information need and then judging the relevance of a retrieved document due to insufficient domain knowledge. The user typically iterates between the tasks of querying and browsing during a search session. In the World Wide Web, for instance, this leads to a style of interaction where a search engine is used to form queries, followed by browsing around the Web pages returned by the search engine, followed by further searching.

As the space of electronic documents increase, along with the number of users and the different styles of usage, a smaller proportion of the many possible meaningful relationships between texts are captured through authored links. This leads to a need for more personalization and customization of hypertext. This need can be addressed through the use of adaptive and dynamic hypertext.

3. Dynamic Hypertext and Adaptive Hypertext

A link is a point within one hypertext node from which one can traverse to another node. This general notion of a link can be instantiated in many ways. One link can point to multiple documents. The link can actually be selected from a list of possible texts based on a profile of user characteristics (e.g., knowledge of a given topic area) or other criteria. A number of methods have been proposed for this type of adaptive linking [Brusilovsky 1996], including link sorting, link annotation, and link hiding. Earlier work on computed and adaptive linking included the implicit linking mechanism described by DeRose [DeRose 1989], generalized hypertext envisioned by Bieber and Kimbrough [Bieber 1992], and the discussion of dynamic adaptation provided by Stotts [Stotts 1991].

Adaptive approaches typically modify the availability of accessibility of links based on characteristics of the user or task. For instance, in the COOL link model [Wantz 1997], an evaluation function selects from a set of destination resources (e.g., URLs) in a multi-ended link, based on a user's profile. In contrast, dynamic links are created at run-time rather than being generated earlier (precomputed links) or through modification of or selection from existing sets of links (adaptive links).

One approach to dynamism in hypertext focuses on computing links based on relationships or similarities between texts or passages of text. In this approach, the link is not defined as a pointer from one hypertext node to another, but rather as a query that leads to a different node. Different forms of link types can then be envisioned based on how and when a query is constructed. Precomputed links can be constructed at any time, whereas dynamic links are computed at the moment they are required [Ashman 1997]. An example of a precomputed link would be a link from a politician's name occurring anywhere in a hyperbase (e.g., a website for the Australian parliament) to the biographical details for that politician contained in the handbook for the legislature [Thistlewaite 1997]. The advantage of such a precomputed link is that it could regulate all such instances of politician's names, and it could be updated automatically as the composition of the legislature changed. In contrast, a dynamic query (computed at run-time) can take into account the specifics of the current user interaction. The query might be based on a combination of the browsing history, user profile, content of the current document, etc. In this approach, dynamic hypertext represents an intermediate point on a continuum between querying and browsing [Waterworth 1991].

In one form of query-based dynamic linking, queries are marked up directly on texts while they are being read [Golovchinsky 1993], [Golovchinsky 1993a]. For instance, clicking on the word "hypertext" and then dragging with the mouse button down to the word "search" (at which the point the mouse button is raised), would form the query "hypertext AND search". This form of query markup has been shown to yield reasonable results in large-scale text retrieval tasks [Charoenkitkarn 1995]. The querying interface can be further modified so that users simply click on previously marked up text or phrases (e.g., marked up in blue with underlines, to imply the presence of a hypertext link). The text markup is created based on terms that have been previously selected, content-bearing words related to those terms, and possibly automated indexing techniques (e.g., using term-frequency based measures developed for information retrieval [Salton 1989]), including phrase identification methods. The sentence that the link (i.e., the marked up text that was clicked on) occurs in is sent to a search engine as a query. It is assumed that the user selects a particular link due to an interest in the content surrounding the link. The most relevant node to the query becomes the endpoint for the selected link. This creates a hypertext "point and click" interface to an underlying search functionality [Golovchinsky 1997].

Query-based dynamic hypertext can look and feel like a static hypertext system. Interaction consists of clicking on marked up words or phrases in the text, which are then treated as if they were links. In experimental testing of this type of system [Tam 1997] [Tam 1997a], users perceived the system to be a human-authored static hypertext, in spite of the fact that it was actually working as a search system with a highly simplified user interface. For further description of this query-based model of dynamic hypertext see [Bodner 1997], [Tam 1997a].

3.1 Properties of Dynamic Hypertext

Dynamic hypertext unifies querying and browsing by providing a browsing point and click front-end or interface to searching functionality. It also avoids the need for mode switching (or spikiness) between searching and browsing, as frequently happens when using search engines on the Web. The same interface is seen at all times, that is text, which can be read or clicked on to move to related material which is also presented as a page of text. Moving to related material is based on a search query. However, the user may interpret this movement as search or as a link traversal, depending on the look and feel of the interface, or the training or instructions that are provided. The available research results indicate that dynamic hypertext can be both an effective interface for text retrieval and a satisfactory implementation of hypertext. Dynamic hypertext, even with future advances in algorithms and methodology, is unlikely to challenge well crafted and targeted hypertexts created by human authors. However, for large scale collections it has the significant advantage of not requiring additional authoring effort once the text for the nodes or documents in the hyperbase has been written. Dynamic hypertext will generally work best when the text is well written and when the vocabulary used is reasonably consistent across the document collection.

Query-based dynamic hypertext can be used in conjunction with static or adaptive hypertext since links are simply added to what is previously available. The dynamic hypertext is also self-customizing, since the links that are presented by the system, and the implementation of those links, depends on the history of the userĖs interaction with the system. This "user profile" changes the apparent behaviour of the system from user to user and from session to session.

The surprising property of the dynamic hypertext system is that the same system can be used as a hypertext [Tam 1997], or as an effective text retrieval system [Bodner 1999]. In this grey area between querying and browsing, the apparent nature of the system depends on the perception of the user and the nature of his or her task motivation.

The query-based approach to dynamic hypertext is also amenable to "weak authoring" approaches, that allow authors to express relationships without forcing readers to deal with fixed structures or follow specific paths. These weak authoring approaches allow authors to specify rules concerning how dynamic links are to be constructed based on user selections within marked up texts in various contexts.

Arguments in favour of query-based dynamic hypertext include: a simplified interface to search functionality, reduced authoring effort, and greater opportunity for customization based on the current user's interaction history or specific task context. An additional benefit is decreased cost of maintenance, since dynamic links do not get broken, and new material is automatically available for dynamic linking (i.e., automated updating of the implied hypertext structure is a side effect of dynamic linking). However, disadvantages include computation of each link at run-time (instead of using stored, precomputed links), which can be expensive in a large system with many users [Ashman 1997]; over-completeness, which occurs when the reader is presented with more links then he/she can comprehend [Thistlewaite 1997]; and problems with "paradoxical" or false links. False links may occur because of polysemy, i.e., multiple word senses that lead the search algorithm to incorrectly judge the similarity of text fragments. This may lead to unsound links [Thistlewaite 1997] in the hypertext. While our experience has been that the advantages of query-based dynamic hypertext seem to outweigh the disadvantages in the research environments that we have studied, further research is needed to determine when it should be used in applied settings.

4. Conclusions

The concept of hypertext subsumes a broad family of models that share the concept of links as connections between nodes (usually segments of text). Several classes of adaptive and dynamic hypertext have been proposed, and the pursuit of dynamism and adaptation in hypertext continues to be actively researched. Links can be authored, computed, annotated and filtered, among other operations. This flexibility with respect to how links are created, computed, and selected is creating new opportunities for personalization and customisation of hypertext. In the future, we can expect more sophisticated methods of user profiling, semantically richer techniques for building relationships between different texts (see [Kopak 1999] for a discussion on link types), and new methods of authoring that define rules for how links might be created or filtered.

Acknowledgements

This research was supported by grants from Communications and Information Technology Ontario (CITO) and the National Science and Engineering Research Council of Canada (NSERC) to the second author. The authors would like to thank John Waterworth, Nipon Charoenkitkarn, Bernd Nordhausen, Felix Valdez, and Jim Tam for contributing to our research on dynamic hypertext. We would especially like to acknowledge Gene Golovchinsky's role in developing the query-based model of dynamic hypertext. Finally, we would like to thank the reviewers of this paper for their insightful comments.

References

[Ashman 1997] Helen Ashman, Alejandra Garrido, and Harri Oinas-Kukkonen. "Hand-made and Computed Links, Precomputed and Dynamic Links" in Proceedings of Multimedia '97 (HIM '97), Germany, 191-208, 1997.

[Baird 1989] Patricia Baird and Mark Percival. "Glasgow On-line: Database Development using Appležs HyperCard" in Hypertext: Theory into Practice, Ray McAleese (editor), Oxford: Intellect, 1989.

[Bieber 1992] Michael Bieber and Steven O. Kimbrough, "On Generalizing the Concept of Hypertext" in MIS Quarterly, 77-93, March 1992.

[Bodner 1997] Richard C. Bodner, Mark H. Chignell, and James Tam. "Website authoring using dynamic hypertext" in Proceedings of Webnet'97, Toronto: Association for the Advancement of Computing in Education, (1997), 59-64, 1997.

[Bodner 1999] Richard C. Bodner and Mark H. Chignell. "ClickIR: text retrieval using a dynamic hypertext interface" in Proceedings of the Seventh Text Retrieval Conference (TREC-7), Gaithersburg, Maryland: National Institute of Standards and Technology (NIST), 1999.

[Brusilovsky 1996] Peter Brusilovsky. "Methods and Techniques of Adaptive Hypermedia" in User Modeling and User-Adapted Interaction 6, 87-129, 1996.

[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.

[Campagnoni 1989] F. R. Campagnoni and Kate Ehrlich. "Information Retrieval using a Hypertext-based Help System" in ACM Transactions on Office Information Systems, 7(3), (1989), 271-291, 1989.

[Charoenkitkarn 1995] Nipon Charoenkitkarn , Mark H. Chignell, and Gene Golovchinsky. "Interactive Exploration as a Formal Text Retrieval Method: How Well can Interactivity Compensate for Unsophisticated Retrieval Algorithms?" in Proceedings of the Third Text Retrieval Conference (TREC-3), Harman, D.K. (editor) NIST Special Publication 500-225. Gaithersburg, Maryland, 179-199, 1995.

[Conklin 1987a] Jeff Conklin. "Hypertext: An Introduction and Survey" in IEEE Computer, 20(9), 17-41, September 1987.

[Cooke 1989] Peter Cooke and Ian Williams. "Design Issues in Large Hypertext Systems for Technical Documentation" in Hypertext: Theory into Practice, Ray McAleese (editor), Oxford: Intellect, 1989.

[DeRose 1989] Steven J. DeRose. "Expanding the Notion of Links" in Proceedings of ACM Hypertext '89, Pittsburgh, PA, 249-257, November 1989.

[Golovchinsky 1993a] Gene Golovchinsky and Mark H. Chignell. "Queries-r-links: Graphical Markup for Text Navigation" in Proceedings of INTERCHI ž93, Amsterdam: The Netherlands, 454-460, 1993.

[Golovchinsky 1993] Gene Golovchinsky. Queries-r-links: Query-Based Browsing in Full-Text Retrieval Systems, M.Sc. Thesis, Department of Industrial Engineering, University of Toronto, 1993.

[Golovchinsky 1997] Gene Golovchinsky. From Information Retrieval to Hypertext and Back Again: The Role of Interaction in the Information Exploration Interface, Ph.D. Thesis, Department of Mechanical and Industrial Engineering, University of Toronto, 1997.

[Kopak 1999] Richard W. Kopak. "A proposal for a taxonomy of functional link types" in ACM Computing Surveys, Symposium on Hypertext and Hypermedia, 2000.

[Nielsen 1990a] Jacob Nielsen. "The Art of Navigating through Hypertext" in Communications of the ACM (CACM), 33(3), 297-310, March 1990.

[Parunak 1989] H. van Dyke Parunak. "Hypermedia Topologies and User Navigation" in Proceedings of ACM Hypertext '89, Pittsburgh, PA, 43-50, November 1989.

[Salton 1989] Gerald Salton. Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer. Addison-Wesley, Reading, MA, 1989.

[Stotts 1991] P. David Stotts. "Dynamic adaptation of hypertext structure" in Proceedings of ACM Hypertext '91, San Antonio, TX, 219-231, December 1991.

[Tam 1997] James Tam. Design and Evaluation of Web-based Dynamic Hypertext, Ph.D. Dissertation, Department of Mechanical and Industrial Engineering, University of Toronto, 1997.

[Tam 1997a] James Tam, Richard Bodner, and Mark Chignell. "Dynamic hypertext benefits novices in question answering" in Proceedings of the Human Factors and Ergonomics Society 41st Annual Meeting, (1997), 350-354, 1997.

[Thistlewaite 1997] Paul Thistlewaite. "Automatic construction and management of large open webs" in Information Processing and Management, 33(2), 161-173, 1997.

[Wantz 1997] L. Jay Wantz and Michael Miller "Toward user-centric navigation of the Web: COOL links using SPI" in Proceedings of the Sixth International World Wide Web onference, Santa Clara, CA, April 1997.

[Waterworth 1991] John A. Waterworth and Chignell, M. H. "A model of information exploration" in Hypermedia 3(1), (1991), 35-58, 1991.


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.