Adaptive Dynamic Hypertext based on Paths of Traversal

Nathalie Mathe ( (415) 604-3515

Jim Chen ( (415) 604-1139

Advanced Interaction Media Group

Computational Sciences Division, MS 269-2

NASA Ames Research Center

Moffett Field, CA 94035-1000

1. Introduction

In our User Modeling 94 Conference paper "A User-Centered Approach to Adaptive Hypertext based on an Information Relevance Model", we presented an adaptive technique to interactively acquire and refine indexing knowledge of conceptual relevance. The model, called a compositional relevance network, employed a simple adaptive algorithm embedded in a dynamic indexing architecture based on user feedback. The relevance network model was incorporated in a hypertext document system, and worked in conjunction with other hypertext features by providing additional user-centered conceptual indices. The adaptive mechanism did not involve directly existing hyperlinks. In this short work paper of our ongoing research, we report briefly, an extension to the original compositional relevance network model, and how the extended model can be applied to hypertext navigation.

2. Compositional Relevance Network

The relevance network provides a compositional indexing mechanism to facilitate mapping between query descriptors and related references. The model basically consists of two major components: a mechanism to create and maintain useful composite indices, and an algorithm to record, propagate and derive referential relevance information associated with these indices.

Composite indices are small sets of query descriptors established in accordance with user queries. Relevance information of references associated with these indices are recorded based on user feedback, as adjusted frequencies of successful retrieval. Composite indices which are subsets of other composites subsume relevance feedback from their supersets. When a query is presented to the system, composite indices corresponding to the largest subsets of the query composition are used to derive the set of references relevant to the query.

The usefulness of a composite index is maintained through usage, more specifically, by tracking the number of times a composite has been used to derive query results, with or without feedback. Less useful composite indices are replaced by newly created ones, both to ensure efficient computation, and to facilitate an effective conceptual indexing structure which warrants better generalization.

In the original model, a new composite index is created upon the presentation of a new user query. The new index has the same composition as the set of descriptors of the query. Such an approach has the disadvantage that small but useful combinations of descriptors, which are not likely to be used as full queries, have lesser chance of becoming composite indices. The current version of the relevance network employs a different approach. Co-occurrence statistics of query descriptors are collected across user queries. Pairs of descriptors of high co-occurrence measures are then selected to become new composite indices. In addition to individual descriptors, existing composites are also included in the co-occurrence data collection process, hence larger compositions of descriptors can be established incrementally.

To summarize briefly, the compositional relevance network memorizes user-centered referential relevance information through user feedback, and facilitates the derivation of generalized information through the subsumption of relevance feedback and the development of an effective dynamic indexing architecture.

3. Adaptive Dynamic Hypertext

The compositional relevance network described above can be easily modified to foster an adaptive dynamic hypertext system. A dynamic hypertext system generates hyperlinks at run time based on current context. Traditionally, hyperlinks from a hypertext node provide connections to information directly related to the content of that node. In a user-centered approach, many other kinds of connections may be desirable to facilitate rapid and effective access to information in a large multi-media document space. Unfortunately, large number of hyperlinks from a single node not only can be detrimental to the presentation interface, but also can potentially aggravate the "lost in hyperspace" problem. A dynamic hypertext interface provides a filtered view of hyperlinks according to current needs. Such filters can be implemented statically as rules or procedures embedded in a hypertext system, or, as proposed here, can be incorporated as a user-centered adaptive mechanism based on navig! ation history.

More specifically, we propose here an adaptive hypertext system which incrementally learns and creates dynamic hyperlinks to shorten the distance of traversal, based on statistics of frequently used traversal paths by individual users. During hypertext navigation, dynamic hyperlinks of the current node are filtered by the current traversal path which lead to this node.

3.1 Composite Nodes

Similar to a set of query descriptors in the relevance network, a traversal path in adaptive hypertext can be defined as an ordered set of nodes. Instead of deriving reference information from composite indices which are subsets of a current query, dynamic hyperlinks are generated by composite nodes corresponding to subpaths which lead the navigation to a current node.

Similar to the co-occurrence data used to select composite indices, statistics of hyperlink traversal between nodes can be collected. Links of high traversal frequencies are selected to become composite nodes, which are then entered into the data collection process. Thus traversal statistics can be collected not only on a link between two nodes, but also on a link from a composite node, i.e., a path, to a node. Hence composite nodes corresponding to longer paths can be established incrementally.

3.2 Dynamic Hyperlinks

The adaptive dynamic hypertext model differs much from the relevance network model in that the output references are hyperlinks themselves. A dynamic hyperlink is created through a process similar to that of the creation of composite nodes. However, instead of collecting statistics of immediate traversal, i.e. moving directly from one node to another, co-occurrence data between ordered pairs of remotely linked nodes within the same session of navigation is used. The purpose of establishing composite nodes is to filter navigation by the current path of traversal, hence the exact sequence from one node to another must be maintained.

The purpose of creating dynamic hyperlinks, on the other hand, is to provide users with hyperlinks which facilitate rapid information access, hence the exact traversal sequence between nodes is ignored. A new hyperlink from a composite node, i.e., a subpath, to a hypertext node is dynamic since it is filtered by the path used to arrive at the last node of the subpath. A hyperlink established between two basic nodes, on the other hand, is always displayed without filtering.

Filtering of dynamic hyperlinks in the adaptive hypertext model is done by combining hyperlinks associated with the particular composite nodes which correspond to paths that, firstly, are subpaths of the current navigation path, and secondly, end at the same current hypertext node.

3.3 Computational Issues

Combinatorially there are many more possible traversal subpaths than there are query subsets, hence the workspace needed to accommodate different composite nodes for an adaptive dynamic hypertext system can be overwhelming. A more aggressive composite node maintenance procedure must be carefully devised. The statistical selection process used in node creation needs to be adjusted by the size of composites. The composite node replacement process needs to be controlled by the frequency of traversal. The filtering process in adaptive dynamic hypertext, on the other hand, is less expensive than the relevance derivation in the relevance network. This is because all useful composite nodes must follow exactly the same sequence of nodes as the current navigation path and arrive at the same current node.

4. Summary

We have reported a variation of the relevance network model which can be applied to adaptive hypertext systems. Development of this model is currently in progress. While much experimental effort is needed to validate the approach, we believe that our proposal provides a good foundation for a significant research area in adaptive dynamic hypertext systems.