Many websites offer their users a lot of freedom to navigate through a large hyperspace. Some sites offer navigation or orientation support in the form of (complete or partial) site maps or guided tours. Some sites also use adaptive hypermedia techniques such as link annotation to help users find their way, based on an individual or group user model. In such systems the navigation support is often tied to the existing link structure. In this paper we discuss how websites can also offer adaptive navigation and orientation support like site maps and guided tours that are independent of the underlying link structure of the website. In particular, we show how the AHAM model, introduced in [5], can represent such adaptive global or local orientation support. To this end we define Link-Independent Navigation Support (LINS) that provides the user a better understandable navigation environment and a strong connection among pages at different abstraction levels in hyperspace. AHAM provides a design platform to define all kinds of relationship graphs, called abstract views in this paper. Abstract views describe connectivity among concepts independently from the basic link structure of the underlying hyperspace, and LINS is based on abstract views.
adaptive hypermedia, user modeling, navigation support, hypermedia reference model, adaptation rules.
The introduction of World Wide Web has made hypermedia the preferred paradigm for user-driven access to information. Websites typically offer users a lot of freedom to navigate through a large hyperspace. Unfortunately, this rich link structure of hypermedia applications may cause some usability problems:
Adaptive hypermedia systems (AHS) in general, and adaptive websites in particular aim at overcoming the navigation and comprehension problems by providing adaptive navigation support and adaptive content. The adaptation (or personalization) is based on a user model that represents relevant aspects of the user such as preferences, knowledge and interests. We focus on simple Web-based systems that can only gather information about the user by observing the browsing behavior of that user. Each time the user "clicks" on a link the system uses the selected link to update the user model and to adapt the presentation accordingly. Also, in this paper we concentrate on adaptive navigation support, not on adaptive content. More specifically we study navigation support that is independent of the website's fixed link structure. (The topics we do not describe can be found in earlier papers, like [5] and [10].)
The basic idea with adaptive navigation support is to adapt the link structure in such a way that the user is guided towards interesting, relevant information, and kept away from non-relevant information. Typical link-adaptation tries to simplify the rich link structure to reduce orientation problems, while maintaining a sufficient level of navigational freedom, typical of hypermedia systems. Brusilovsky [1] mentions the following link-adaptation methods:
Guidance can be provided in hypermedia applications where users have some goal in terms of information they want and where browsing is the preferred or only way to find the required information. Global guidance means that the system suggests navigation paths on a global scale, like with guided tours. This is for instance useful in educational websites. When a user wishes to learn about a certain topic, the system may suggest a set of pages to read, along with an indication of a desired or at least a meaningful reading order. Local guidance means that the system suggests the next step to take, for instance through a "next" or "continue" button. When the user deviates from the suggested path, new suggested continuations are generated on the fly.
Orientation support means that the system presents an overview of the global (link) structure of the hyperspace (global orientation support), or of a part thereof that is near the user's "current" position (local orientation support). The system also indicates that "current" position in this structure. Brusilovsky in fact also mentions "personalized goal-oriented views" as an adaptation method. We regard this as an extension of global orientation support: Each "view" may be a map or list of links to all pages or sub-parts of the whole hyperspace that are relevant for a particular working goal. Like with guided tours, the link structure presented in these views may be generated for the specific user, and not part of the "fixed" link structure of the website. In this paper we are particularly interested in such adaptively generated link structures, which we shall call abstract views.
In previous research we have shown that our AHAM model [5] can be used to describe link adaptation, as used in systems that guide users towards interesting information by changing the presentation of link anchors. In general however, adaptation of the existing link structure alone is not enough to solve all users' navigation and orientation problems:
To improve the basic adaptive navigation support in AHS, we propose link-independent navigation support to supplement the above cases. Link-independent navigation support (or LINS) aims to guide the user through hyperspace through an abstract view based on the user's preferences. It uses extra connections among concepts through certain relationships. Link adaptation techniques, e.g. adaptive link annotation can be used in addition, to provide guidance even within the abstract view. LINS can of course also be combined with the existing link structure, possibly also made adaptive, to provide an even richer personalized navigation environment.
While LINS could be investigated at a more general level, we concentrate on its use in AHS that can be described in the AHAM model. Such systems maintain a user model by tracing the user's browsing behavior and perform adaptation based on that user model. AHAM is well suited to describe many Web-based AHS. With LINS we consider how to describe adaptive Open Hypermedia Systems in AHAM.
This paper is structured as follows: in Section 2 we briefly review the AHAM reference model, thereby concentrating on the parts that are needed to describe adaptation functionality at an abstract level. Section 3 discusses how to provide LINS through the concept of abstract views. It also describes the generation and adaptation of navigation and orientation support (based on views) in the database-like language we introduced in [10]. Section 4 draws conclusions and provides an outlook into our future work.
Many adaptive hypermedia systems share parts of their architecture. Just like the Dexter model [7][8] tried to capture the facilities offered by hypermedia systems of its time (and of potential future systems), AHAM [5], (for Adaptive Hypermedia Application Model) describes the common architecture of adaptive hypermedia systems. Part of this common architecture is typical for Web applications: their event-driven nature, where each page access results in a user-model update and an adaptive presentation. AHAM's overall structure is an extension of that Dexter model. According to AHAM each adaptive hypermedia application is based on three main parts:
The division into a domain model (DM), user model (UM) and adaptation model (AM) provides a clear separation of concerns when developing an adaptive hypermedia application. The main shortcoming in many current AHS is that these three factors or components are not clearly separated. Modeling an existing AHS in AHAM may not be straightforward because AHAM requires these parts to be made explicit, and the adaptive behavior to be described using adaptation rules. However, using AHAM enables us to clearly describe how an AHS works, how different AHS compare, and also how to design new and more powerful AHS.
The AHS consists not only of the three sub-models (mentioned above) but also of an adaptation engine (AE). The AE describes implementation dependent aspects of the AHS. In previous work [10] we described design issues for a general-purpose AE, and defined AHAM CA-rules (condition-action rules) to illustrate how sets of rules work together. We will use these rules to describe the generation and browsing through LINS in Section 3.
Figure 1 shows the overall structure of an adaptive hypermedia application in the AHAM model. The figure has been made to resemble the architecture of a hypermedia application as expressed in the Dexter Model [7][8].
In this section we only present the elements of AHAM that we will need to discuss how Link-Independent Navigation Support (LINS) can be expressed in AHAM.
The domain model of an adaptive hypermedia application consists of concepts and concept relationships. Concepts are objects with a unique object identifier, and a structure that includes attribute-value pairs and a sequence of anchors.
A concept represents an abstract information item from the application domain. It can be either an atomic concept or a composite concept.
The composite concept hierarchy must form a DAG (directed acyclic graph). Also, every atomic concept must be included in one or more composite concepts. Figure 2 illustrates a part of a concept hierarchy.
A concept relationship is an object (with a unique identifier and attribute-value pairs) that relates a sequence of two or more concepts. Each concept relationship has a type. The most common type is the hypertext link. In AHAM we consider other types of relationships as well, which play a role in the adaptation, e.g. the type prerequisite. When a concept C1 is a prerequisite for C2 it means that the user "should" read C1 before C2. This does not imply that there must be a link from C1 to C2. It only means that the system somehow takes into account that reading about C2 is not desired before some (enough) knowledge about C1 has been acquired. Through link adaptation the "desirability" of a link will be made clear to the user. Figure 3 shows a small set of (only binary) concepts associated to one another by three types of concept relationships: prerequisite, inhibit, and link.
Apart from the "implicit" relationship type and set of relationships that form the concept hierarchy an AHS need not contain or support any other relationships. AHAM can thus also represent applications without traditional hypertext links (like e.g. in spatial hypertext [9]). A relationship graph defines a certain view to reflect a relationship among the set of pages. In Section 3 we will use relationship graphs to define abstract views to provide link-independent navigation support to supplement the basic adaptive navigation support in AHS.
The atomic concepts, composite concepts and concept relationships together form the domain model DM of an adaptive hypermedia application.
A user model consists of named entities for which we store a number of attribute-value pairs. For each user the AHS maintains a table-like structure, in which for each concept in the DM the attribute values for that concept are stored. Because there can be many relationships between abstract concepts and concrete content elements like fragments and pages, a user model may contain many attributes per concept to indicate how the user relates to the concept. Typical attributes would be knowledge level (e.g. in educational applications) and interest (e.g. in encyclopedia, museum sites, or on-line mail-order catalogs). The user model may also store information about what a user has read about a concept, and for how long or how long ago, etc. Concepts can furthermore be used (some might say abused) to represent "global" user aspects such as preferences, goals, background, hyperspace experience, or a (stereotypical) classification like student, employee, visitor, etc. For the AHS or the AHAM model the true meaning of concepts is irrelevant.
In the sequel we will always consider UM as being the user model for a single user. In this paper we do not discuss adaptation to group behavior.
The AHAM model targets adaptive hypermedia applications that follow the request-response paradigm that is typical for the Web. The interaction with the system is described through events generated by the user (or by an external source). Each event triggers user model updates and results in an adaptive presentation. In [10] we introduced a database-like language to express the effects of user actions as condition-action rules (AHAM CA-rules). This implies that we do not explicitly model events as events, but as updates to attributes that trigger rules. Accessing a web-page for instance will result in a Boolean "access" attribute of the page (in the user model) to become true. The small example below illustrates the structure of these rules. (A syntax description can be found in [10].)
C: select P.access A: update F.pres := "show" where F in P.fragments and F.relevance = "recommended"
In this example we first see that the condition for this rule is that P.access has become true for some page P. When this happens (and because there is no additional where clause in the condition) the action is executed. In the action we look at fragments F of page P. If a fragment is marked as "recommended" then that fragment will be shown. This is indicated as a presentation specification and represented as a "pres" attribute of the fragment. Note that because abstract concepts, pages and fragments appear in the domain model as well as the user model (but with different attributes) we take the liberty of mixing both in the adaptation rules. E.g. our notation F in P.fragments in fact refers to the concept hierarchy from the domain model, whereas P.access and F.relevance for instance refer to attributes in the user model.
Note that the AHAM CA-rule language is just a vehicle for describing how an AHS should perform user model updates and adaptation. It does not imply that we require an AHS to use such a language. Even when an AHS has only a built-in behavior, we can still describe this using the AHAM CA-rule language. Also, we partition adaptation rules into phases to indicate that certain rules must always be executed before certain other rules. The phases include IU, the initialization of the user model, UU-pre, the user model updates that are performed before generating the presentation, GA, the generation of the adaptation, and UU-post, the user model updates that come after the presentation. The phases are a convenience for ensuring that the execution of the rules has desirable properties such as termination and confluence, as discussed in [10].
An AHS does not only have a domain model, user model and adaptation model, but also an adaptation engine, which is a software environment that performs the following functions:
The adaptation engine thus provides the implementation-dependent aspects, while DM, UM, and AM describe the information and adaptation at the conceptual, implementation independent level. Note that DM, UM and AM together thus do not describe the complete behavior of an AHS. The same set of adaptation rules may result in a different presentation depending on the execution model of the adaptation engine.
In adaptive hypermedia applications, an author defines abstract relations between concepts and between concepts and pages, in order to enable the system to automatically generate user-guidance. This abstract information is normally hidden from the user. Users benefit from these (invisible) relationships through adaptive navigation support based on these relationships. A typical example is adaptive link annotation based on prerequisites, as exemplified by applications of the Interbook system [2]. In such applications the navigation support augments the existing link structure. In this paper we describe link-independent navigation support (LINS):
Section 3.1 explains how to apply these ideas within the AHAM framework. Section 3.2 explains how to update the user model for generating the LINS. Section 3.3 explains how to generate adaptive navigation support based on views. Section 3.4 explains how to infer cross-references for each pag that has implied connections to other abstract concepts. Section 3.5 explains how to show the content of the nodes for link-independent navigation support.
The link structure is not the only information can be used to generate navigation support. In fact in some systems the author must define some abstract relational requirement among pages to provide the navigation support. AHAM provides a platform to define these relational requirements as relationship graphs, called abstract views in this paper. Different users may want to use different views to navigate through hyperspace. In figure 4, e.g., user A visits the hyperspace through views P or Q, and user C visits the hyperspace through views R or S. User B, however, visits the hyperspace using no view, i.e. she uses the basic link structure. Link-independent navigation support can be tailored to the user's preferences through the selection of an appropriate view. This corresponds to the selection of linkbases as done in [3] and [6].
We consider views separately when we provide link-independent navigation support. We don't consider the combination of several views in this paper. Each view corresponds to the relationship graph of a specific relationship type. A view gives a certain perspective on a set of concepts connected to a set of pages. It consists of two parts: one consists of concept nodes that represent abstract concepts, and edges that represent the same type of relationships among concepts; another part consist of page nodes and links from the parent concepts in the concept hierarchy. Figure 5, e.g., could be an index view describing a (hyper)book, or a structure of prerequisite relationships. R(C1, C2) describes that relationship between C1 and C2. L(C4, P1) describes a link from C4 to P1.
The author can build navigation support based on views to suggest to the user (possibly several) ways to explore the subject. While AHAM provides a mechanism to define relationships and a rule-system to make use of them, no assumptions are made as to the semantics of any relationship. This is the author's responsibility. We summarize three steps to define a view:
Relationship graphs are not required to be directed acyclic graphs (DAG) as in Figure 5. However, for many types of relationships cycles are a sign of bad design, e.g., with prerequisite or inhibit relationships. Views play an important role in maintaining the user model and generating basic adaptation in AHS [10]. In Interbook [2] for instance there is a "teach me" button that is used to generate a set of links to all pages that contribute knowledge about a certain concept. This is a nice way to use views, and in fact offers link-independent navigation support. In subsection 3.3 we focus on how to generate LINS based on views and the user model.
We briefly illustrate how the AHAM CA-rules are used to perform user model updates, in which the concept relationships play a role. Adaptation is normally based on relevance of or recommendations for concepts or pages. This is in turn deduced from aspects like interest or knowledge (which must exceed some threshold to be considered sufficient to be taken into account). Below we give a possible rule that decides whether a concept should be recommended based on whether the user has enough knowledge about all prerequisite concepts.
C: select C2.knowledge
where C2.knowledge >= C2.threshold
A: update C1.relevance := "recommended"
where Prerequsite(C2, C1) and
not exists (select C3
where Prerequsite(C3, C1)
and C3.knowledge < C3.threshold)
The rule is triggered when the knowledge of concept C2 is changed and when that knowledge then matches or exceeds the required knowledge threshold for C2. The action of the rule sets the relevance value for C1 to "recommended" if there are no unsatisfied prerequisites left for C1. (For efficiency reasons only concepts C1 are considered for which C2 is a prerequisite. Other concepts cannot be influenced by the knowledge change for C2.
In order to describe the user model updates, changes to relevance of pages, and also the resulting adaptation one needs many rules. We don't describe them here, not just because of the size restrictions for this paper, but also because every AHS has a different behavior and thus also a different description using AHAM CA-rules.
With several examples we will illustrate how AHAM CA-rules can be used to perform adaptation for navigation support pages. In Section 2.3 we indicated that rules are divided into phases to simplify scheduling their execution. The rules we describe here all belong in the GA (Generate Adaptation) phase. This means that when we reach this phase user model updates, like deciding which concepts or pages should be recommended, have already been performed (in the UU-pre phase). Assume G represents a view (for a relationship type G). We can use this view to provide four types of navigation support: "global orientation", "local orientation", "global guidance" and "local guidance". For simplicity we assume that attributes "g-o", "l-o", "g-g" and "l-g" of G are used to trigger the generation of the different types of navigation support. We shall ignore the user model updates needed to select which type of navigation support the user wants.
"Global orientation support" based on view G means that the system presents an overview of the whole (relationship) structure of the view G. It is generated through the rules below. In the view we use colors as an annotation technique for showing the relevance of page nodes. We have taken the "traffic light metaphor" in which green represents recommended, red represents not-recommended, and yellow represents not-interesting.
C: select G.g-o
A: update F.pres := "green"
where F in G.children and F.relevance = "recommended"
C: select G.g-o
A: update F.pres := "red"
where F in G.children
and F.relevance = "not-recommended"
C: select G.g-o
A: update F.pres := "yellow"
where F in G.children and F.relevance = "not-interesting"
Sometimes it is very useful to show the user's current page in "global orientation support". This rule shows the "current page" in another color, e.g. black, in the orientation support. We can create an attribute "current" of G (or a global variable), and update it in the UU-pre phase with the rule:
C: select P.access A: update G.current := P
The above rules then need to be modified so they check that F is not the current page, and we add a rule:
C: select G.g-o
A: update F.pres := "black"
where F in G.children and G.current = F
"Local orientation support" based on view G means that the system presents only a part of the (relationship) structure of the view G. The scope for local orientation support may be only all ancestors of the current page (up to the root of the view if that exists, i.e. if the view is acyclic and thus has a root) or only concepts and pages that are a fixed number of steps (relationships or links) away from the current page. Ancestors, parents, children, brothers, etc., can all be easily expressed using rules. We omit this to keep the paper short (and readable). A possible rule for "local orientation support" based on view G could be:
C: select G.l-o
A: update F.pres := "green"
where F in G.children and (Brother(F, G.current)
or Ancestor(F, G.current))
and F.relevance = "recommended"
Rules for other levels of relevance are similar of course. The above rule will present sibling pages of the current page and ancestor concepts of the current page using the color "green" if these pages or concepts are "recommended".
"Global guidance" based on view G means that the system presents a list of pages to read, in a certain order. (Abstract concepts are not pages one can read and thus can be part of an overview but not of some kind of guided tour.) The suggested order of the pages depends on relevance. Expressing this is easiest using an "external" function, although it could be done through a series of rules that together perform sorting based on relevance. (If relevance has only three values the function is simple, but some AHS may have a numerical relevance value requiring complete sorting.) We will ignore the sorting issue here.
C: select G.g-g
A: update F.pres := "green"
where F in G.children and F.relevance = "recommended"
and exists (select C
where L(C, F))
Note that L(C, F) expresses that F is a page. Rules for other levels of relevance are similar.
"Local guidance" based on view G means that the system presents only the next step or steps to take, based on the view. We give a simplified rule below that assumes the concepts linked to pages provide a sequence through relationships. In general however one may need to go higher up in the view.
C: select G.l-g
A: update F.pres := "green"
where F in G.children and F.relevance = "recommended"
and exists (select C1
where L(C1, F) and (L(C1, G.current) or
exists (select C2
where G(C2, C1) and
L(C2, G.current) ) ) )
This rule shows that recommended pages that are linked to the same concept as the current page, or to a concept that is one step away (in the current view) will be shown as recommended (with a green link).
Once more, rules for other levels of relevance are similar.
The system can infer a cross-reference relationship for each page to all its connected abstract concepts defined in all views. These cross-references can be shown as a part of original page or in a separate page depending on the system. Cross-references can be very useful in IR systems when users do not know what they want before they find something interesting in current page. A page may connect with several abstract concepts in one view; it may also connect with several abstract concepts in different views. A cross-reference contains a list of links that can be grouped according to the type of view, for example, so that the user can easily find related concepts without getting disoriented in the hyperspace. The cross-references can be adaptive also in the sense that they reflect the knowledge state is for every referenced concept. The author gets these cross-references for free because the system can infer them from the abstract views defined in the DM.
In the previous sections we described how to generate link-independent navigation support through AHAM CA-rules. Now we briefly discuss what the system should present when a user "clicks" on a concept link in LINS, e.g. in the view presented as "global orientation support". (These rules also belong in the GA phase.)
When users "click" on a node of a concept link in LINS, the system can generate a page that contains some description about the concept, and a list of links to its sub-concepts down to the page level. The links in this page will be presented using color metaphors as used for adaptive annotation to show the knowledge state for all links to pages and nodes.
Here is a rule example that says when a user "clicks" on a concept node in global orientation support or local orientation support, the system shows the fragment of description of this node in the page. Such support only works if a "description" attribute is available for abstract concepts.
C: select C.access A: update F.pres := "show" where C.description = F
The following rule describe that when a user "clicks" on a concept node, the system shows all the sub-concept links of this concept using the color metaphor as for adaptation annotation.
C: select C.access A: update F.pres := "green" where (G(C, F) or L(C, F)) and F.relevance = "recommended"
Again, the rules for other relevance levels are similar. What the above two rules do not yet express is how the description and the links to sub-concepts will be combined into a single page to present to the user.
This paper proposed the idea of providing link-independent navigation support (LINS) based on abstract views in AHS. LINS provides users extra ways to browsing hyperspace through abstract relationships. It is a supplement to adaptive navigation support based on the basic link structure of hyperspace. We described how to generate and use LINS in AHAM, a general reference model for AHS. This also shows that AHAM is capable of expressing LINS without the need for extensions to the model. By using LINS users can browse hyperspace in a better understandable navigation environment.
Our method assumes that authors define the abstract views before the system generates the LINS. The LINS is very useful in educational hypermedia for instance because teachers would provide the abstract views for the courses. It is less practical in large information systems (without a clear notion of an "author", because our method does not provide for the automatic generation of the abstract views.
Our future work is twofold: first we wish to continue to show that AHAM can express the functionality of many existing AHS and that it is a useful framework to compare adaptive applications and to describe their functionality in a unified way. (This will be a significant part of the forthcoming thesis of the first author.) Secondly we wish to build a system that incorporates many of the ideas of AHAM. To this end we are adding functionality to the AHA! system [4], thanks to a grant of theNLnet Foundation.