Adaptive Dynamic Hypertext based on Paths of Traversal
Nathalie
Mathe (mathe@ptolemy.arc.nasa.gov) (415) 604-3515
Jim
Chen (jchen@ptolemy.arc.nasa.gov) (415) 604-1139
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.