=Paper=
{{Paper
|id=Vol-473/paper-1
|storemode=property
|title=Here you can download the complete proceedings as a single PDF-file (~1,7MB)
|pdfUrl=https://ceur-ws.org/Vol-473/proceedings.pdf
|volume=Vol-473
}}
==Here you can download the complete proceedings as a single PDF-file (~1,7MB)==
https://ceur-ws.org/Vol-473/proceedings.pdf
Proceedings of the
First International Workshop on
Dynamic and Adaptive Hypertext:
Generic Frameworks, Approaches and Techniques
(DAH’09)
Paul De Bra, Mykola Pechenizkiy
Eindhoven University of Technology (TU/e), Netherlands
debra@win.tue.nl; m.pechenizkiy@tue.nl
Copyright © 2009 for the individual papers by the papers’ authors.
Copying permitted for private and academic purposes. Re-publication of material
from this volume requires permission by the copyright owners.
Preface
Dynamic generation of hypertext and its adaptation and personalization to particular users is a
powerful and useful concept. It is particularly helpful for the reduction of the information overload
such as is frequently experienced on the Internet. But it is equally helpful for guiding users towards
“interesting” topics, products, artifacts or descriptions thereof in electronic shops, libraries or
museums, or for filtering appropriate items from a general or domain-specific news feed.
Reference models and generic architectures unify a community and provide a leading generic
model and/or architecture that spawns research activities in many directions. Examples of such generic
models are AHAM for adaptive hypermedia and FOHM for open hypermedia. A nice example of a
resulting generic implementation is the AHA! system that was last described in ACM Hypertext'06.
The research fields of hypertext and adaptive hypermedia (or adaptive web-based information
systems) however, have been growing rapidly during the past ten years and this has resulted in a
plethora of new terms, concepts, models and prototype systems. As a result the established models no
longer include many of the recent new concepts and phenomena. In particular, open corpus adaptation,
ontologies, group adaptation, social network analysis and data mining tools for adaptation are not or at
least insufficiently supported.
The DAH'09 workshop1 organized in conjunction with the 20th ACM International Conference
on Hypertext and Hypermedia and held on June 29, 2009, in Turin, Italy. The workshop provides a
focused international forum for researchers to discuss new developments in generic methods and
technologies for dynamic and adaptive hypertext. Topics discussed during the workshop include:
adaptation and personalization including such issues as open-corpus adaptation, group adaptation,
higher order adaptation, and sharing of user models; adaptive and dynamic hypertext authoring (e.g.
authoring conceptual adaptation models); service-oriented approaches for adaptation; use of data
mining for user and domain modeling, and automatic generation of adaptation rules.
These proceedings include six accepted contributions to the workshop. We would like to thank
the authors for their interest in the workshop and for submitting their contributions. Special thanks to
the PC Members for their help in reviewing the submitted papers.
The first paper by Levacher et al. “A Framework for Content Preparation to Support Open-
Corpus Adaptive Hypermedia” proposes a novel framework for open-corpus content preparation that
allows processing documents existing in open and closed corpora and producing coherent conceptual
sections of text with associated descriptive metadata. This work is important for enabling the
mainstream adoption of AHS in web applications, which is impossible without enabling the
repurposing existing content. The authors adopt state-of-the-art information extraction and structural
content analysis techniques for an on-demand provision of tailored, atomic information objects.
Next contribution by van der Slijs et al. “GAL: A Generic Adaptation Language for describing
Adaptive Hypermedia” argues that despite a large variety of personalization and adaptation features
that different emerging Web applications offer, it is possible to distinguish a central and unifying
objective of adaptive engines that facilitates these various features, that is, to create an adaptive
navigation structure. The authors present Generic Adaptation Language (GAL) that specifies the
engine independent basic adaptive navigation structure that allows using any authoring environment in
combination with any adaptive engine as long as there is a corresponding GAL compiler.
The following two papers present the service-based view on the development of adaptive
hypermedia. Harrigan and Wade in “Towards a Conceptual and Service-Based Adaptation Model”
consider the limitations of the current practice in adaptation modeling which assume that concepts and
relationships between concepts are the fundamental building blocks of any adaptive content and
introduce a representation of a conceptual and service-based adaptation model. With their approach
1
The scientific programme overview, and other workshop-related information as well as the link to the online
proceedings can be found at http://www.win.tue.nl/~mpechen/conf/dah09/.
I
having additional expressive power it would be possible to facilitate activity-based and process-
oriented adaptive applications, including the adaptation of the process itself.
Koidl et al. in “Non-Invasive Adaptation Service for Web-based Content Management Systems”
consider the architectural and technical issues related to provision of third party adaptive services
pluggable into existing web-based content management systems (WCMS) like Wiki. The authors
introduce a third party Adaptive Service that also contributes to mainstreaming the adoption of AHS.
This work introduces a principled way of embedding adaptive technologies within existing WCMS
allowing to reduce or avoid the expense of re-engineering such systems.
The paper by Hargood et al. “Investigating a thematic approach to narrative generation” considers
the potential, the challenges and open issues in integrating themes in narrative generation systems that
attempt to generate content within a narrative or story framework.
Knutov et al. in “Versioning in Adaptive Hypermedia” present an approach that reuses the key
concepts and ideas behind versioning and applies them to the adaptive hypermedia field. The authors
illustrate with a couple of intuitive examples how such an approach helps to facilitate authoring,
managing, storing, maintenance, logging and analysis of behaviour because of providing more
flexibility and maintainability of the systems. Particular, versioning helps to create, maintain and re-
use concurrent versions of an application or a model or a particular property and value, saving
authoring effort and that is not less important facilitating provenance analysis.
Eindhoven Paul De Bra
June 2009 Mykola Pechenizkiy
II
Organization
Organizing Committee
- Paul De Bra, Eindhoven University of Technology, the Netherlands
- Mykola Pechenizkiy, Eindhoven University of Technology, the Netherlands
Programme Committee
- Peter Brusilovsky, University of Pittsburg, USA
- Dominik Heckmann, DFKI, Germany
- Nicola Henze, University of Hannover, Germany
- Geert-Jan Houben, Delft University of Technology, the Netherlands
- Riccardo Mazza, SUPSI, University of Lugano, Switzerland
- David E Millard, University of Southampton, UK
- Vincent Wade, Trinity College Dublin, Ireland
- Yang Wang, University of California, Irvine, USA
III
IV
Table of Contents
Killian Levacher, Eamonn Hynes, Seamus Lawless, Alex O'Connor and Vincent Wade
A Framework for Content Preparation to Support Open Corpus Adaptive Hypermedia .................... 1
Kees van der Sluijs, Jan Hidders, Erwin Leonardi and Geert-Jan Houben
GAL: A Generic Adaptation Language for describing Adaptive Hypermedia.................................. 13
Martin Harrigan and Vincent Wade
Towards a Conceptual and Service-Based Adaptation Model ........................................................... 25
Kevin Koidl, Owen Conlan and Vincent Wade
Non-Invasive Adaptation Service for Web-based Content Management Systems.............................. 37
Charlie Hargood, David E. Millard and Mark J. Weal
Investigating a thematic approach to narrative generation ............................................................... 49
Evgeny Knutov, Paul De Bra and Mykola Pechenizkiy
Versioning in Adaptive Hypermedia .................................................................................................. 61
V
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
A Framework for Content Preparation to Support
Open-Corpus Adaptive Hypermedia
Killian Levacher, Éamonn Hynes, Séamus Lawless, Alexander O'Connor,
Vincent Wade
Centre for Next Generation Localisation, Knowledge & Data Engineering Group,
School of Computer Science and Statistics, Trinity College, Dublin, Ireland
{Killian.Levacher, hynese, Seamus.Lawless, Alex.OConnor,
Vincent.Wade}@cs.tcd.ie
Abstract. A key impediment for enabling the mainstream adoption of
Adaptive Hypermedia for web applications and corporate websites is the
di culty in repurposing existing content for such delivery systems. This
paper proposes a novel framework for open-corpus content preparation,
making it usable for adaptive hypermedia systems. The proposed frame-
work processes documents drawn from both open (i.e. web) and closed
corpora, producing coherent conceptual sections of text with associated
descriptive metadata. The solution bridges the gap between information
resources and information requirements of adaptive systems by adopting
state-of-the-art information extraction and structural content analysis
techniques. The result is an on-demand provision of tailored, atomic in-
formation objects called slices. The challenges associated with open
corpus content reusability are addressed with the aim of improving the
scalability and interoperability of adaptive systems. This paper proposes
an initial architecture for such a framework in addition to reviews of
associated technologies.
Key words: Open Corpus Content, Adaptive Hypermedia, Statistical
Content Analysis, Structural Content Analysis
1 Introduction
The increasing pervasiveness of the internet is fundamentally changing how peo-
ple author, interact with and consume content. There are early signs of a shift
in the way digital content is created, from the linear authoring and publication
of material towards the aggregation and re-use of existing content from various
disparate sources.
Adaptive Hypermedia Systems (AHS) have traditionally attempted to de-
liver dynamically adapted and personalised presentations to users through the
sequencing of recon gurable pieces of information.
While the eectiveness and bene ts of such systems have been proven in
numerous studies [1][2], a major obstacle to their widespread adoption relates to
1
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
the restriction of suitable content available to provide such adaptivity in terms
of volume, granularity, style and meta-data.
One of the key impediments in oering a wide range of information objects is,
for example, the considerable amount of manual eort involved in creating these
resources. Information object content consists of either pre-existing documents
[3], or of content created by small groups of individuals [4], intentionally authored
for a particular system [5]. This generates both scalability and interoperability
issues, which prevents the mainstream adoption of adaptive systems.
Metadata standards such as LOM [6] attempt to provide generic content
packaging methods with the aim of enabling the interoperability of information
objects within AHSs. Although they implement usage-agnostic principles, their
development is very time consuming due to the complexity involved [7]. Fur-
thermore, they also require AHSs to comply with a speci c content structure in
order to make full usage of these resources.
In parallel with these developments, a wealth of information is now accessible
on the web, in digital repositories and as part of library initiatives. However, due
to its heterogeneity, this information is not suited to direct usage by AHSs in its
present form. It is available in several languages and within large documents with
very limited meta-data. These objects are also generally very coarse-grained and
correlated with unnecessary noise such as navigation bars, advertisements etc.
Automated content preparation techniques are therefore necessary to provide
scalable solutions to AHS speci c content requirements.
Our goal is to provide AHSs with the ability to bene t from the wealth
of knowledge already accessible on the web and in digital libraries by bridging
the gap between these information resources and the information requirements
of adaptive systems. We propose the creation of a service that can tailor open-
corpus content for use in AHSs without requiring such systems to adopt a generic
content structure. This system would hence resolve scalability issues in content
authoring by providing AHSs with a large array of information objects. More-
over, the inclusion of open corpus information would provide up-to-date content
in a wide variety of styles and structures.
We aim to combine several disciplines such as Information Retrieval, Adap-
tive Web and Information Extraction in order to provide an on-demand informa-
tion object service. This service will harvest open corpus information, segment
it structurally and automatically augment it with successive layers of internal
metadata. Any AHS could then provide this service with a request that includes
requirements for an information object which would in turn fetch and tailor this
content to its speci cation.
This paper is structured as follows: Section 2 will present the key challenges
addressed within this research in relation to AHS information requirements as
well as structural and statistical text analysis. The framework we envisage de-
veloping is presented in detail in section 3, along with the overall work ow pro-
duced. Section 4 will present the application area of such a technology and how
we intend to evaluate it. Finally, section 5 will conclude and present the road
2
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
map ahead. This work is applicable to any type of content, however some of the
examples presented in this paper will be based on adaptive e-learning systems.
2 Key Challenges and Related Work
Throughout the evolution of adaptive systems, technologies introduced have
moved from original "all in one" solutions, towards increasing modularity whereby
AHSs become consumers of domain, pedagogical and user models [8]. This has
the eect of leaving such systems with a core adaptive engine capable of deal-
ing with a wider range of loosely coupled models that are integrated as desired.
Content, however, is still very tightly coupled to these engines and as a result
strongly impedes the general adoption of these systems.
Most AH systems, up until recently have operated in closed document spaces
with content speci cally authored for their usage [4], hence obstructing interop-
erability, both by accepting only a narrow eld of content, and by motivating the
generation of content in a highly-speci c format. As a result adaptive systems
also encounter scalability issues due to the limited amount of content available
to adapt on, arising from the small amount of manual contributions available.
Open corpus content is increasingly seen as providing a solution to these is-
sues [9]. However, most systems incorporating this type of content have, for the
moment, mainly focused on linking it with internal content as alternative ex-
ploration paths. Those incorporating it fully into their system [10][11] require
manual mark-up of such content with speci c meta-data. Schemas such as LOM
(in the area of e-learning) and IMS packagings, attempt to provide usage-agnostic
solutions, however they require a lot of development eort thus prohibiting scal-
ability [7]. Moreover, AHSs must comply with speci c content structures so as to
avail of these resources. In order to leverage the full potential of open corpus re-
sources, adaptive systems need to incorporate and correlate this type of content
fully into existing systems using structure-agnostic and automated approaches.
Our approach, on the other hand, moves away from the packaging model
altogether by considering content as a pluggable feature of adaptive systems to
the same extent as user or domain models. A service providing open corpus con-
tent automatically in a form and format customised for each requesting adaptive
system decouple this feature from current systems, disentangling it from content
provision and hence providing a solution to both scalability and interoperability
issues.
Fully integrating information harvested over the web within adaptive presen-
tations, on the other hand, generates new issues. Web pages are usually written
as stand-alone content without any re-composition purposes. In addition to the
main content, they usually present navigation bars, advertisement banners and
irrelevant features from various sources that must be removed prior to proper
re-use.
Structural segmentation will therefore be an initial fundamental requirement
in tailoring open corpus content for use within adaptive systems. A large propor-
3
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
tion of pages harvested will need to be stripped of any redundant information
that might prevent its adequate re-use in adaptive systems.
The problem of structural segmentation has already been addressed from
dierent perspectives mainly with the purpose of tailoring existing content for
dierent displays [12]. Most of the techniques up until recently have focused
on analyzing the DOM structure of a HTML page as a basis for segmentation.
Several attempts, for instance, focus on removing templates from pages by iden-
tifying common DOM sub-trees [13] or using isotonic regression [14]. Machine
Learning algorithms are also used to decide which pair of tags should coincide
with suitable segmentation points. However, it has become increasingly popu-
lar to separate any formatting style from within HTML tags using Cascading
Style Sheets (CSS) and Javascript, thus increasing the heterogeneity of rendered
content from similar HTML trees [15]. For this reason, such techniques do not
appear to be an adequate solution when dealing with a large set of documents
as diverse as the World Wide Web.
Vision-based techniques, using entropy reduction [12], or techniques such as
VIP algorithms [16] on the other hand, partition a page based on its rendering.
These have the bene t of covering a wider range of pages regardless of their
HTML trees. But their usage within systems dealing with large volume of data is
questionable since rendering must be performed prior to any analysis, inevitably
producing delays. Moreover, they completely ignore DOM features altogether
which do provide structural clues where rendered surfaces appear similar [12].
This part of our research will therefore seek to provide a solution to this
paradigm that scales both in terms of processing speed as well as structural
segmentation precision within a wide heterogeneous range of pages. The proce-
dure will additionally need to incorporate the notion of granularity in order to
keep cohesive chunks of text together to provide meaningful input to subsequent
semantic analysis.
Within the statistical analysis component of the framework, it is important
to extract concepts with high precision/recall and e ciently represent these con-
cepts in such a way as to make them as interoperable and re-usable as possible.
Brusilovosky et al. [9] discuss the lack of re-usability and interoperability between
adaptive systems and how current adaptive hypermedia systems are restricted
to closed corpora by the nature of their design. This framework architecture
is based on the idea that open corpus adaptive hypermedia is feasible: the ef-
fort will be in moving away from tables of document-term frequencies towards
a richer semantic representation of data that is uncomplicated, easy-to-use and
highly interoperable.
3 Framework for Content Preparation
The framework proposed in this research is divided into three separate com-
ponents as shown in gure 1. Each part of the framework executes a speci c
task on the open corpus content. A speci c layer of meta-data is subsequently
appended, enriching it with structural and semantic clues for further analysis at
4
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
each step. The rst two stages of the pipeline are executed pre-emptively prior
to any client request while the intelligent slicing task is executed at run time.
The concept of a slice is an abstract notion representing a stand-alone piece
of information, originally part of an existing document, extracted and segmented
to ful l a speci c information request. A slice can be atomic or composed of
other slices. It possesses its own set of properties (or meta-data) and can inherit
those of others. A slice is virtual in the sense that it only exists temporarily to
ful l a client request. It is speci c to each information request and represents a
subjective perspective on a particular piece of a document and its description.
The degree of complexity of a slice will match the requirements of the system
which requests it.
The rest of this section will present in detail each stage of the framework.
The structural analysis of open corpus content will initially be described followed
by the statistical analysis of these resources. Finally, the overall work- ow be-
tween this framework and AHSs clients will be outlined using intelligent slicing
technology.
Fig. 1. Content analysis methodology
3.1 Structural Analysis
In order to provide the initial structural segmentation needed to create slices,
this research will attempt to combine bene ts of both DOM- and vision-based
segmentation techniques. The process will initially divide pages in atomic blocks
using relevant HTML tags similar to [15]. Following this extensive break down,
the page will be reconstructed, aggregating relevant blocks together with similar
inherent textual properties. Changes in text ow (short phrases in navigation
bars vs. long sentences in text), for instance, will be considered as segment
delineations.
5
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
The notion of text density, originating from the eld of computer vision will
also be applied to these pages using the ratio between the number of words and
the space occupied on the page [15] as an additional hint for section divisions.
Furthermore, the use of linguistic analysis techniques such as style boundary
detection will be considered as additional boundary indication.
3.2 Statistical Analysis
In this section we discuss methods for statistically analysing text and extracting
information such that it can be used as part of the wider framework; it serv-
ing as a substrate for the incorporation of several dierent statistical analysis
techniques. In order for the proposed framework to be able to interact naturally
with information seekers, it must cope with inherent ambivalence, impreciseness
or even vagueness of requests and deal with them in a structured and systematic
fashion. For these reasons, statistical methods oer a wealth of neat techniques
for dealing with the underlying complex characteristics of language.
Work currently underway includes looking at methods for the automatic
extraction of concepts from text. The vision is to extract and create a conceptual
layer over the text which is amenable to e cient searching and logical reasoning.
We move away from working only on closed-corpus texts and go some way to
addressing the huge challenge that is the open domain problem [9] by making
our algorithms as generalised as possible and not restricted to any particular
domain. One method for identifying concepts from text is to use supervised
learning methods. We use HMMs (Hidden Markov Models) to extract coherent,
relevant passages from text [17]. This method is particularly suited to extraction
from expositional texts as opposed to highly expressive literary texts (i.e. poetry,
literary prose, etc.) which have high entropy vocabularies and diverse language
use. Jiang et al. report very high precision/recall compared to other methods and
their work ts in nicely with the idea of extracting concepts/coherent relevant
passages of text.
The basic idea is as follows: given some a priori concept that is to be extracted
from a text, several passages identi ed as being associated with that particular
concept are used as training data for the HMM classi er. Once a reasonable
amount of training data has been collected (enough data such that the classi er's
train and test error converges towards the desired performance), the HMM can
then make soft decisions on a text stream and identify coherent relevant passages
of varying length with very high accuracy.
The topology of the HMM is shown in gure 2 below: the states B1, B2 and
B3 are the background states, state E is an end state and state R is a relevant
state. The 5 state HMM structure allows the system to emit a relevant symbol,
move to a background state and then re-emit a relevant symbol at some later
point before reaching the E state. The output observation probabilities can be
extracted directly from the training corpora, and the objective is to learn the
transition probabilities so as to maximise the likelihood of observing a relevant
passage given a concept.
6
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Fig. 2. HMM topology
On a synthesised corpus consisting of a number of article abstracts (coherent
relevant passages) stitched together, with each abstract having an associated
label, very high precision and recall values were reported [17]. It remains to be
seen how well the HMM method performs on non-synthetic corpora and work is
currently underway to explore this.
Several extensions to the work of Jiang et al. have also been explored, includ-
ing the incorporation of anaphora to resolve pronouns and augment the presence
of important entities such as people and places. In addition to the uni-gram lexi-
cal features, more elaborate query expansion methods and semantic analysis has
been looked at to extract more elaborate features for the classi er to work from.
The incorporation of this additional functionality is expected to yield higher
performance in terms of precision and recall on the synthetic document set and
more reliable performance on real corpora. Instead of just a single-dimension
vector with just one feature (i.e. a stemmed word), the word is represented
as a slightly higher dimensional vector (i.e. the stemmed word with additional
features) that helps improve the overall accuracy of the classi er.
Word Sense Clustering Another method used to extract conceptual enti-
ties from text is word sense clustering. Lexical resources such as WordNet [18]
provide ne-grained sense descriptions for a huge number of words in the En-
glish language. However, such ne-grained detail is not always required: it is
possible to cluster together word senses and come up with a looser word sense
that abstracts away a lot of the detail and is more compatible with the frame-
work as described in this paper. Snow et al. [19] describe a supervised learning
method for merging word senses using a SVM-based (Support Vector Machine)
clustering algorithm. This algorithm yields senses at a slightly higher level of
granularity and is more compatible with corporation into a conceptual layer
representation. Use of latent semantic indexing techniques is another powerful
and elegant method for dealing with synonymy and polysemy whilst at the same
time, automatically generating concepts, or clusters of word senses [20]. In la-
tent semantic indexing, each document is represented as a vector of terms, with
7
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
each element of the vector having an associated weight; some function of the
term frequency. Dimensionality reduction techniques are then applied to each of
these document vectors, resulting in a set of vectors that point in the direction
of semantically similar words. Each term in a document can then be projected
onto the reduced-dimensionality semantic space, where the dominant vector(s)
correspond to the concept that the term is most associated with. Probabilistic
latent semantic indexing techniques [21] provide an even more accurate means
of mapping from terms to concepts and such techniques will be used extensively
for the statistical analysis component of the framework.
Representing content in the form of a semantic map is thought to mimic the
way the human mind classi es linguistic categories. While there is no direct link
between semantic maps and the representation of concepts in the human mind,
it is an objective starting point for investigation of the e ciency of the semantic
map representation on human cognition.
3.3 Content Preparation Work-Flow
The framework architecture presented in gure 3 belongs to the core functional
unit of a web service that delivers on-demand slices to adaptive systems.
As a content provider, the framework will rst of all require domain speci c
data gathered previously by pre-emptive crawls in areas of interest to adaptive
engine consumers. We envisage as an initial step to use the OCCS harvesting
system [22], developed previously, as a content gathering tool in order to boot-
strap this framework with a renewable wide range of content. The system will
be content harvester agnostic, hence any other content gathering system could
be plugged in if required, such as private repositories for instance.
Once suitable content is available, the framework described previously will
rstly remove any redundant content, then hand over only relevant information
to our semantic analysis unit, and then create a conceptual map of the data.
These two steps will produce a large amount of internal meta-data, both from a
semantic and structural point of view.
At this stage, the service will be ready to receive content requests from a
diverse range of consumers through conceptual queries which the service will at-
tempt to map as closely as possible to the internal meta-data gathered previously
on its content. The intelligent slicing unit will be responsible for matching re-
quests to available data within the system and slicing information objects to the
nest semantic grain possible matching the query. Semantic maps constructed a
priori will be used to produce a personalised slice for the adaptive systems. Se-
mantic technologies (OWL and SPARQL) will form the underlying mechanism
navigating through pre-emptive semantic mappings.
4 Evaluation and Roadmap
This section provides a brief summary of what are the main bene ts of this
framework in comparison to traditional systems. The limitations of this archi-
tecture are also discussed along with possible solutions. This will result in a
8
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
9
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
steps will be necessary to ultimately provide a reliable foundation for the PMCC
application envisaged.
5 Discussion
This paper described how restrictions in the provision of suitable content for
Adaptive Hypermedia Systems currently impedes their full mainstream adoption
due to interoperability and scalability authoring issues. The decoupling of con-
tent infrastructures from Adaptive Systems along with the use of automatically
tailored open corpus resources was presented as a solution to this predicament.
Consequently, the architecture for a content provision service that lls the
gap between open corpus information resources and Adaptive System informa-
tion requirements, was outlined. To the best of our knowledge, this framework
represents the rst attempt to produce a pipelined, client agnostic, information
preparation service that produces virtual content slices for adaptive systems.
Other innovations in the framework architecture include the modular and plug-
gable open corpus analysers, which produce successive layers of internal meta-
data information. The combination of these components and how they integrate
coherently to produce the framework is also an aspect under investigation.
An initial prototype of this framework is currently under development and
aims towards integrating fully with a customer care information system that is
currently being deployed as part of the Centre for Next Generation Localisation
project.
Acknowledgements This research is supported by the Science Foundation
Ireland (grant 07/CE/I1142) as part of the Centre for Next Generation Locali-
sation (www.cngl.ie) at Trinity College, Dublin. The authors wish to thank the
anonymous reviewers for their comments.
References
1. Brusilovsky, P.: Adaptive Navigation Support in Educational Hypermedia: An
Evaluation of the ISIS-Tutor. Journal of Computing and Information Technology
(1998)
2. Hook, K.: Evaluating the utility and usability of an adaptive hypermedia system.
International Conference on Intelligent User Interfaces (1997)
3. Henze, N., Nejdl, W.: Adaptivity in the KBS Hyperbook System. 2nd Workshop
on Adaptive Systems and User Modeling on the WWW (1999)
4. Dieberger, A., Guzdial, M.: Coweb - Experiences with Collaborative Web Spaces.
Interacting with Social Information Spaces (2002)
5. De Bra, P.: Teaching Hypertext and Hypermedia through the Web. Journal of
Universal Computer Science 2 (1996)
6. IMS Global Learning Consortium: Learning Object Metadata (LOM) Information
Model 1.2.2 (2009)
10
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
7. Farrell, R.G., Liburd, S.D., Thomas, J.C.: Dynamic Assembly of Learning Objects.
In: Proceedings of the 13th International World Wide Web Conference on Alternate
Track Papers & Posters. (2004) 162169
8. Conlan, O., Wade, V., Bruen, C., Gargan, M.: Multi-model, Metadata Driven Ap-
proach to Adaptive Hypermedia Services for Personalized eLearning. In: Adaptive
Hypermedia and Adaptive Web-Based Systems. Springer-Verlag (2002) 100111
9. Brusilovsky, P., Henze, N.: The Adaptive Web. In: Open Corpus Adaptive Edu-
cational Hypermedia. Springer (2007) 671696
10. Henze, N., Lenski, W., Wette-Roch, E.: Adaptation in Open Corpus Hypermedia.
Journal of Arti cial Intelligence in Education 12 (2001) 325350
11. Carmona, C., Bueno, D., Guzman, E., Conejo, R.: SIGUE: Making Web Courses
Adaptive. In: Adaptive Hypermedia and Adaptive Web-Based Systems. (2002)
12. Baluja, S.: Browsing on Small Screens: Recasting Web-Page Segmentation into
an E cient Machine Learning Framework. In: Proceedings of WWW-2006, ACM
(2006) 3342
13. Vieira, K., da Silva, A.S., Pinto, N., de Moura, E.S., Cavalcanti, J.M., Freire,
J.: A Fast and Robust Method for Web Page Template Detection and Removal.
In: Proceedings of the 15th ACM International Conference on Information and
Knowledge Management, ACM (2006) 258267
14. Chakrabarti, D., Kumar, R., Punera, K.: Page-Level Template Detection via Iso-
tonic Smoothing. In: Proceedings of the 16th International Conference on World
Wide Web, ACM (2007) 6170
15. Kohlsch, C., Nejdl, W.: A Densitometric Approach to Web Page Segmentation.
In: Proceedings of the 17th ACM Conference on Information and Knowledge Man-
agement, ACM (2008) 11731182
16. Cai, D., Yu, S., Wen, J.R., Ma, W.Y.: Extracting Content Structure for Web Pages
Based on Visual Representation. Springer (2003)
17. Jiang, J., Zhai, C.: Extraction of Coherent Relevant Passages using Hidden Markov
Models. ACM Transactions on Information Systems (TOIS) 24 (2006) 295319
18. Fellbaum, C.: WordNet: An Electronic Lexical Database. MIT Press (1998)
19. Snow, R., Prakash, S., Jurafsky, D., Ng, A.Y.: Learning to Merge Word Senses.
In: EMNLP. (2007)
20. Deerwester, S., Dumais, S., Furnas, G., Landauer, T., Harshaman, R.: Indexing
by Latent Semantic Analysis. Journal of the American Society for Information
Science 41 (1990) 391407
21. Hofmann, T.: Probabilistic Latent Semantic Indexing. In: 22nd Annual Inter-
national ACM SIGIR Conference on Research and Development in Information
Retrieval. (1999)
22. Lawless, S., Hederman, L., Wade, V.: Occs: Enabling the Dynamic Discovery,
Harvesting and Delivery of Educational Content from Open Corpus Sources. In:
Eighth IEEE International Conference on Advanced Learning Technologies, IEEE
Computer Society (2008) 676678
11
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
GAL: A Generic Adaptation Language for describing
Adaptive Hypermedia
Kees van der Sluijs1, Jan Hidders2,
Erwin Leonardi2, Geert-Jan Houben1,2
1
Eindhoven University of Technology
PO Box 513, NL-5600 MB Eindhoven, The Netherlands
k.a.m.sluijs@tue.nl
2
Delft University of Technology
PO Box 5031, NL-2600 GA Delft, The Netherlands
{a.j.h.hidders, e.leonardi, g.j.p.m.houben}@tudelft.nl
Abstract. Nowadays, Web applications have become more sophisticated and
interactive, and many of them also offer personalization and adaptation as their
features. The mechanisms for these features are typically built on top of specific
adaptive engine that has its own engine-specific adaptation language that can be
very different from other engines. However, our observation leads to the fact
that the main objective of these adaptive engines is the same, that is, to create
adaptive navigation structure. In this paper, we present GAL (Generic
Adaptation Language) that specifies the basic adaptive navigation structure in
an engine independent way. Since GAL is generic, it can be compiled to
difference specific adaptive engine and be used in combination with different
authoring environments.
Keywords: GAL, generic adaptation language, navigation specification
1. Introduction
With the evolution of the Web, Web applications have grown more complex,
interactive and more and more they try to adapt to the user. Personalization and
adaptation are important features on the Web, as the Web allows a large and diverse
public with diverse goals and demands to use the same Web applications.
Personalization and adaptation are needed to help tailoring suboptimal one-size-fits-
all solutions to an experience that fits a certain user in a certain context.
Adaptivity and personalization are complex mechanisms to build from scratch.
Therefore, past research resulted in a number of adaptive engines and frameworks that
simplify the creation of adaptive applications, like [1,2,3,4]. Also several authoring
environments have been built that target the simplification of the creation of adaptive
applications. If in the educational domain, for instance, a teacher should be able to
create an adaptive course in such an adaptive engine, the authoring environment
should allow such a lay user (in terms of adaptive systems) to easily create an
adaptive application. Authoring environments also allow having different perspectives
on adaptive applications, e.g. consider workflow or goal-oriented views.
13
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
A complicating factor however is that authoring environments are typically built
on top of a specific adaptive engine, i.e. using a specific authoring environment
restricts the specific adaptive engine that you may use and choosing a specific
adaptive engine restricts the authoring environment that you can use. Moreover, we
found that the different engines (even different versions of the same engines) typically
have very different and sometimes complex engine specific languages that you need
to use for specifying an adaptive application. However, even though the different
adaptive engines have different functionalities and different strengths and
weaknesses, in the end the core of these engines achieve the same thing: they create
an adaptive navigation structure.
In this paper we present the Generic Adaptation Language (GAL). GAL is a
language that allows expressing adaptive navigable Web applications over a given
dataset. It is engine independent as it captures the basic adaptive navigation structure
that is used by all (more specific) adaptive engines. This structure refers to the
underlying dataset via queries. GAL is based on our previous experience with
building Web applications in Hera [4]. However instead of specifying the whole
applications design (domain, navigation, presentation), in GAL we focus on the
adaptive navigation.
The primitives of the GAL language should are chosen such that they support the
basic types of adaptation as specified in the field of adaptive hypermedia [5]. To show
that GAL is generic we will build compilers that allow compiling GAL to several
specific adaptive engines. This allows a new authoring environment to author
applications for all those engines by just providing support for the GAL language as
an output format. Similarly compilers will be built from several existing authoring
environments to GAL, which allows a new adaptive engine to use existing authoring
environments by adding support for the GAL language.
Our claim is that by using this GAL language we are able to use any authoring
environment in combination with any adaptive engine (for which we write a
compiler). GAL adds the additional benefit of having the code in one place in an
orderly way with a simple easy to understand syntax in semantics. We will give well
defined semantics, which adds additional benefits like adding model checking
functionality at the GAL level, so that a GAL engine can abstract away some of the
tasks of the adaptive engine.
The structure of the rest of the paper is as follows. In Section 2 we first discuss
some related work. After that, we present the formal syntax and an informal semantics
of GAL with a running example that presents an adaptive application about the Milky
Way. In Section 3 we describe the basic concepts of GAL and how it models the
navigational structure of a web site. In Section 4 we describe the global structure and
semantics of a GAL program. In Section 5 we explain how in GAL the components of
pages are defined. In Section 6 we describe the navigation semantics of GAL
programs, i.e., what operations are executed in which order when a user navigates
through the defined web application, and what are the pages presented to the user.
Finally in Section 7 we present our conclusions and discuss future work.
14
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
2 Related Work
Since more than a decade ago, the Web Engineering community has proposed
numerous web engineering methods (e.g. Hera [4], OOHDM [6], WebML [7], and
UWE [8]) for covering complete web application development cycle. These methods
try to separate Web application into three main design concerns: data design,
application design, and presentation design. Some of these methods offer techniques
for adaptation. In [4], an adaptive Web information system called Hera is presented.
Hera focuses on adaptation in the navigational design. RDF is used for expressing the
domain and context data, and the adaptive navigation. In addition, Hera also provides
facility to use RDF query expressions in the definition of application model. This
allows a more fine-grained specification of adaptation and context-dependency.
OOHDM [6] supports adaptation by specifying conditions on navigation concepts and
relationships in the navigation class model. These conditions determine the visibility
of content and links. In WebML [7], navigational adaptation conditions are specified
in a profile as queries. The Event-Condition-Action (ECA) rules are also applied in
WebML in order to attain context-awareness. UWE [8] is an UML-based web
engineering approach that uses OCL constraints on the conceptual model to specify
adaptation conditions. The aspect-orientation is also applied to UWE in order to
specify several types of adaptive navigation, namely, adaptive link hiding, adaptive
link annotation, and adaptive link generation.
In the field of adaptive hypermedia adaptive engines are built that serve
applications which are personalized for their users (which is a characteristic that they
share with for example Hera). Some well known adaptive hypermedia systems
include AHA! [2], InterBook [3], and APeLs [1]). AHA! is an Open Source adaptive
hypermedia system mainly used in education domain. It supports adaptation in a
number of different ways, namely: adaptive guiding, link annotation, link hiding, and
adaptive presentation support, by using conditional fragments and objects. Interbook
provides an environment for authoring and serving adaptive online textbooks. It
supports adaptive navigation that guides the users in their hyperspace exploration.
The guidance is visualized by using annotations (e.g. icons, fonts, and colors).
Adaptive Personalized eLearning Service (APeLS) is a multi-model, metadata drive
adaptive hypermedia system that separates the narrative, content, and learner into
different models. The adaptive engine in APeLS is a rule-based engine that produces
a model for personalized courses based on a narrative and the learner model.
The researchers in adaptive hypermedia also propose several formal models for
adaptive hypermedia applications, e.g. AHAM [9], The Munich Reference Model
[10], and XAHM [11]. AHAM and The Munich Reference Model extend the
DEXTER model [12] by separating the storage layer further. In AHAM, this layer is
separated into domain model, user model, and adaptation model. The Munich
Reference Model divides this layer into domain meta-model, user meta-model, and
adaptation meta-model. While AHAM follows a more database point of view, the
Munich Reference Model uses an object-oriented specification written in the Unified
Modeling Language (UML). The adaptation is performed using a set of adaptation
rules. These models support the content-adaptation and the link-adaptation (or
navigation adaptation). Cannataro et al. proposed an XML-based adaptive hypermedia
model called XAHM [9]. The adaptation process in XAHM is based on three
15
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
adaptivity dimensions that form adaptation space, namely, user’s behavior (e.g.
preferences and browsing activity), technology (e.g. network bandwidth and user’s
terminal), and external environment (e.g. location, time, and language). The
adaptation process is to find the position of the user in the adaptation space. The
user’s behavior and external environment dimensions determine the adaptation of
page content and links. The technology dimension is used in adapting the presentation
layout.
The above state-of-the-arts approaches are different from GAL in the following
ways. Unlike these approaches, GAL is not intended to be another system, method, or
model for designing adaptive applications. Instead, GAL focuses on abstracting from
a specific adaptive engine configuration by generically specifying basic navigation
adaptation in an engine independent way. That is, GAL can be compiled into specific
adaptation engines and used by these engines. Note that GAL does not focus on
typical presentation aspects like text color, font face, and how pages should be
rendered to be presentable on a specific device. These aspects are typically very
engine specific, and therefore hardly describable in a generic way. Moreover, GAL on
purpose separates these concerns and thus limits the number of language constructs in
order to get a clean and simple core language.
3 The Basic Concepts of GAL
The purpose of GAL is to describe the navigational structure of a web application and
how this adapts itself to the actions of the users. The central concept is that of unit
which is an abstract representation of a page as it is shown to a certain user after a
certain request. Basically it is a hierarchical structure that contains the content and
links that are to be shown, and also updates that are to be executed when the user
performs certain actions such as requesting the page or leaving the page. All data
from which these units are generated is assumed to be accessible via a single RDF
query endpoint, and the updates are also applied via this endpoint. In the examples in
this paper we will use the SPARQL1 query language for referring to and updating
data.
The set U of units contains unordered units and ordered units. These differ in that
the first represents a unit with unordered content, i.e., a bag or multi-set, and the
second has ordered content, i.e., a list. Unordered units are denoted formally as uu(C,
h) where C B(E) describes the content as a bag of content elements (in the set E, to
be defined later) and the relation h ET u UQ defines the event handlers by
associating event types in the set ET with update queries in the set UQ. Here we will
assume that ET = {gal:onAccess, gal:onExit} and UQ describes some set of update
queries over RDF stores. Ordered units are denoted as ou(C, h) where C L(E)
describes the content as a list of content elements and the relation h is as for
unordered units.
The set E of content elements contains (1) attributes representing presentable
content such as text, (2) unit container representing a single nested unit, (3) unit sets
1 http://www.w3.org/TR/rdf-sparql-query/
16
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
representing a nested set of units of the same type, (4) unit lists representing a nested
list of units and (5) links representing navigation links. We denote attributes as at(n, l,
v) with a name n EN {A} representing the name of the attribute, a label l EL
{A} representing a printable label for the attribute and a value v V representing
the value contained in the attribute. Here EN denotes the set of content element names
here assumed to be all URIs minus the special constants gal:_top, gal:_self and
gal:_parent, A a special constant not in EN EL denoting the absence of a name, EL
is the set of content element labels here assumed to be the set of RDF literals and V
the set of basic values, i.e., URIs and RDF literals. Unit containers are denoted as
uc(n, l, u) with a name n EN {A}, a label l EL {A} and a unit u U. The
unit label l represents a presentable label and we assume UL is the set of RDF literals.
The name n is used to refer in other parts of the unit to the position of this unit
container. We denote unit sets and unit lists as us(l, UB) and ul(l, UL) with a label l
EL {A} and as content a bag of units UB B(U) or a list of units UL L(U).
Finally, links are denoted as ln(ut, b, q, be, t) with a unit type ut UT that indicates
the type of unit to which the link points, a binding b : X V that maps variable names
to a value and defines the static parameters of the link, a query q LQ {A} that
computes dynamic parameters of the link, a binding extension function be : X VE
that maps variable names to value expressions to describe additional dynamic
parameters and a target t EN {“gal:_top”, “gal:_self”, “gal:_parent”} that
indicates which unit in the current page will be replaced with the retrieved page. Here
LQ denotes the set of queries over RDF stores that return a list of bindings, UT
denotes the set of unit type which we assume here to be URIs, X is the set of variable
names which we assume here all start with “$” and includes the distinguished variable
$user and VE denotes the set of value expressions which compute a single value
given an RDF store and whose syntax will be defined in more detail later on. The set
of all bindings, i.e., partial functions b : X E, is denoted B.
Note that the above definitions of the set of proper units U and the set of content
elements E are mutually recursive, which can be resolved by stating that we define
them as the smallest sets that satisfy the given definitions. Note that therefore a unit is
essentially a finite tree of content elements.
4 The Global Structure of GAL Programs
We proceed with giving the syntax of GAL along with an informal description of its
semantics. The purpose of a GAL program is to describe how, given a page request in
the form of a unit type, a user identifier and a binding that describes the parameters,
the resulting unit is computed from the current RDF store. The top level of the
grammar looks as follows:
::= * .
::= “[” “]” .
We assume that refers to the set of unit type names UT, and
describes the computation of a unit. For each page request the first with
17
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
the requested unit type determines the result. The request is passed on to this while removing the unit type and user identifier and extending the binding such
that $user is bound to the user identifier. The syntax of :
::= “a” (“gal:unit” | “gal:orderedUnit”) “;”
( )* ( | | |
| )* ( )* .
First the type of the resulting unit is specified, i.e., whether it is ordered or unordered,
then the list of required parameters (excluding the implicit parameter $user) is given,
followed by a list of content element expressions, and finally a list of event handlers
is given.
To illustrate the syntax we look at a use case that uses GAL to specify an adaptive
application. We look at a learning application about the Milky Way. More
specifically, we look at the page that specifies information about a specific planet. We
then declare something like:
:Planet_Unit [ a gal:unit; .. {content specification} .. ]
The syntax of and is defined as follows:
::= “gal:hasInputVariable” “[“ “gal:varName” “;”
“gal:varType” “]” “;” .
::= “gal:onEvent” “[” “gal:eventType” (“gal:onAccess” | “gal:onExit”) “;”
“gal:update” “]” “;”.
Here we assume that describes the set of variables X, and describes the set of domain concepts DC and describes the
set of update queries UQX parameterized with variables from X. The semantics of the
is that it first checks if the current binding indeed defines the required
variables with values that belong to the specified domain concept. If this is not the
case, then the result is undefined. Otherwise the binding is restricted to the specified
variables plus $user and passed to the content element expressions. Depending on the
specified unit type, we compute uu(C, h) or ou(C, h). Here C is either the
concatenation of the lists of content elements computed by the specified content
element expressions or the corresponding bag of content elements. For the content
element expressions we assume that they produce either an empty or a singleton list.
Finally, h associates event types with update queries that are obtained by taking the
specified parameterized update query and replacing the variables with their value in
the binding.
For example, in the running example an input parameter of the unit will indicate
which planet we want to show to user. For this we assume that an incoming link to the
planet unit carries this information in the form of a variable. Therefore the following
will be specified in the content specification:
gal:hasInputVariable [
gal:varName "Planet";
gal:varType Planet;
];
18
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
5 Content Element Expressions
We proceed with the syntax of the different content element expressions, starting with
attributes:
::= “gal:hasAttribute” “[“ ? ? “gal:value” “]”.
::= “gal:name” “;” .
::= “gal:label” “;” .
Here describes the set EN of content element names defined here as the
set of URIs not containing the special constants gal:_self, gal:_parent and gal:top.
The semantics of the is the singleton attribute list [at(n, l, v)] with n the
specified name (or A if it is not specified), l is the resulting literal of the
(or A if it not specified or not a literal) and v the result of . If the result of
is undefined, then the result is the empty list [].
The syntax and semantics of are as follows:
::= | “(” “.” “)” | “[” “gal:query” “]” |
“[” “gal:if” “;” (“gal:then” “;”)? (“gal:else” “;”)? “]” .
Here describes the set of values V which we assume here to be the set of
URIs and RDF literals, and describes VQX, the set of parameterized
queries over an RDF store that return a single value. Based on we define
the earlier mentioned set of value expressions VE as the expressions
without free variables. If the is then this is the result. If it
is “(” “.” “)” then the result is the concatenation of the two
literals that are the result of the two s, and if these do not both result in
literals then the result is undefined. If it starts with gal:query then the result is that of
with the free variables substituted with their value in the current binding.
If it starts with gal:if then the result is defined as follows. If the with free
variables replaced by their value in the current binding returns a non-empty list then
the result of the gal:then is returned, otherwise the result of the gal:else
is returned. If that particular is not present then the result is
undefined.
To illustrate this we now provide some attributes in the running example to show
information about this planet on the screen. For example, we want to print the name
of the planet, and also provide an image of that planet:
gal:hasAttribute [
gal:name planetName;
gal:value [$Planet.name]
];
gal:hasAttribute [
gal:name planetImage;
gal:label ( "Image of: ".[$Planet.name] );
gal:value [ gal:query // url of an appropriate picture
“SELECT ?image_url
WHERE { $Planet :hasAssociatedResource ?image
:type Image;
:url ?image_url.}”
]
];
19
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Note the variable references for the variable named “Planet” by using the $-sign. The
expression [$Planet.name] is a syntactic short-hand for the SPARQL query
expression[gal:query “SELECT ?name WHERE { $Planet name
?name }”] which retrieves the name of the planet indicated by $Planet.
Now suppose we want to add an adaptive attribute that gives ‘beginner’ or
‘advanced’ information about the planet, but only if the user has advanced knowledge
about the concept:
gal:hasAttribute [
gal:name planetInformation;
gal:label "Information: ";
gal:value [
gal:if [ gal:query
“SELECT ?conceptPlanetInstance
WHERE { $User :hasConceptInstance ?conceptPlanetInstance
:name $Planet.name;
:visited ?Visited;
:advancedUserValue ?Advanced.
FILTER (?Visited >= ?Advanced)
}”];
gal:then [$Planet.AdvancedInfo];
gal:else [$Planet.BeginnerInfo];
]
]
The query checks if the user number of visits equals or is greater than the amount
of visits to the concepts that are needed to make a user an advanced user. If this is true
(and the query in the ‘if’ clause returns a result) then the advanced information is
showed, otherwise the beginners information is showed.
The next type of content element we consider is the unit container:
::= “gal:hasSubUnit” “[”? ? “]” “;” .
The semantics of is the singleton unit container list [uc(n, l, u)] where
l is the unit label specified in , n is the unit name indicating the location
specified in and u is the first unit in the unit list constructed by . If the result of is undefined then the result is the empty list [].
The syntax and semantics will be defined later on.
The following types of content element we describe are the list units and set units:
::= “gal:hasListUnit” “[” ? “]” “;” .
::= “gal:hasSetUnit” “[” ? “]” “;” .
The semantics of is the list-unit list [ul(l, LU)] where l is the unit
label specified in and LU is the unit list constructed by .
The semantics of is the same except that LU is replaced with BU, the
corresponding bag of units.
To illustrate the use of unit sets in the running example consider that we want to
show a list of the moons of the planet. We can use the hasSetUnit construct for this.
gal:hasSetUnit[
gal:label "The following Moon(s) rotate around “.[$Planet.name];
gal:refersTo Moon_Unit_Short;
gal:hasQuery "SELECT ?Moon
WHERE $Planet :hasMoon ?Moon";
];
20
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
The hasSetUnit construct executes a query and for every result of that query it will
spawn a unit, in this case a Moon_Unit_Short. For every of those units the query
result will be bound to the ‘Moon’ variable.
The final type of content element that can be specified is the link:
::= “gal:hasLink” “[” ? “]” “;” .
::= “gal:refersTo” “;” .
::= ? * .
::= “gal:hasQuery” “[” “]” “;”
::= “gal:assignVariable” “[” “gal:varName” “;”
“gal:value” “]” “;” .
:= “gal:targetUnit” ( | “gal:_top” | “gal:_self” | “gal:_parent” ) “;” .
Here describes the set LQX of parameterized queries over the RDF store
that return a list of bindings and are parameterized with variables from X. The result
of is the link list [ln(ut, b, q, be, t)] where ut is the unit type specified in
, b is the current binding, q is the but with the free variables
replaced with their value in the current binding, be is the partial function that maps
each in the list to the first associated but with the
free variables in this replaced as specified by the current binding, and
finally t is the target in if this is specified and gal:_top if it is not.
For example, the Moon_Unit_Short that was mentioned in the preceding example
could contain a link to the elaborate description as follows:
:Moon_Unit_Short [
a gal:unit;
gal:hasInputVariable [
gal:varName "Moon";
gal:varType Moon
];
gal:hasAttribute [
gal:name moonName;
gal:label "Moon: ";
gal:value [$Moon.name]
];
gal:hasLink [
gal:refersTo :Moon_Unit_Elaborate;
]
]
Note the hasLink construct that binds to the Moon_Unit_Short, meaning that every
attribute in the unit becomes a link that points to the Moon_Unit_Elaborate unit. By
default the current input variables, in this case $Moon, are passed as parameters of the
link, so it indeed will lead to a page describing the same moon more elaborately.
The final non-terminal we consider is which computes a list of units:
::= “gal:refersTo” “[” “]” “;” .
The result is defined as follows. First, the query in is evaluated, while
replacing its free variables with their value in the current binding, and the resulting
list of bindings is extended with the binding specified by the list of
expressions. Finally, for each of the resulting bindings we use them to extend the
current binding and for this binding evaluate the , and finally collect all the
resulting units in a list.
21
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
We extend the syntax with some syntactic sugar: inside a the
fragment “[” “]” can be replaced by a if in the total expression
this is associated with this . In other words, if a occurs in the
after the gal:refersTo then it is interpreted as the associated “[” “]”. This is illustrated in the preceding example for gal:hasSetUnit.
We conclude the presentation of the syntax an semantics of GAL with a possible
output of the running example. Given the definitions for the Planet Unit it would yield
for a specific instance, for example Jupiter, something along the lines as shown in the
screenshot in Figure 1. This screenshot is based upon a GAL specification that is
compiled to and executed by the AHA!3 engine [2].
Figure 1: Screenshot of an instance of the Planet Unit
6 The Navigation Semantics of GAL
In this section we describe the navigation process that is defined by a certain GAL
program. At the core of the navigation semantics is the previously described
computation of the unit that is the result of the request of a user. The resulting unit
then is presented to the user and becomes the current unit, i.e., the unit that is
currently presented to the user. In addition all the update queries associated with the
gal:onAcess events in it at any nesting depth are applied to the RDF store in some
arbitrary order.
If subsequently the user navigates to an external link then all the update queries
associated in it with the gal:onExit event at any nesting depth are applied to the RDF
store in some arbitrary order. If the user follows an internal link ln(ut, b, q, be, t) in
the current unit, then the following happens. First the target unit in the current unit is
determined as follows. If the target is a unit name then this is the unit in the first unit
container with that name. If it is gal:_self then it is the containing unit, i.e., the unit in
which the link is directly nested. If it is gal:_parent then it is the parent unit, i.e., the
unit which has as a content element a unit container, unit set or unit list that refers to
22
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
the containing unit. If it is gal:_top then it is the root unit of the current unit. If in any
of the preceding cases the result is not well defined then the target unit is the root unit
of the current unit. When the target unit is determined then all gal:onExit events that
are directly or indirectly nested in it are applied to the RDF store in some arbitrary
order.
Then, the binding that describes the parameters is computed as follows: the
binding b is combined with the first binding in the result of q and this in turn is
combined with the binding that is obtained when evaluating be. The resulting binding
is sent together with the specified unit type as a request. Then, if this request results in
a unit, the gal:onAccess update queries in this unit are executed as described before.
In the final step the new current unit is the old current unit but with the target unit
replaced with the resulting unit of the request.
7 Conclusions and Future Work
Many Web application frameworks nowadays offer personalization and adaptation
as their features. However, until now the adaptation mechanisms are typically engine
specific and the adaptation languages used by the adaptive engines are different from
one another. In this paper, we have presented Generic Adaptation Language (GAL)
that aims to capture basic adaptive navigation functionality in an engine independent
way. GAL allows us to use every authoring environment in combination with any
adaptive engines. We gave a formal description of GAL, and demonstrated that GAL
can be used to specify an adaptive application. Currently we work on working out
examples that show that GAL allows every type of adaptivity as specified in [5]. In
further future work we look at building compilers from GAL to several adaptive
engines (e.g. for AHA! version 3, Hera and the GALE engine that is being built in the
GRAPPLE project2). Similarly we will build compilers from several authoring
environments to GAL (e.g. for the Graph Author and the authoring tools within the
GRAPPLE project). We expect that our formal work as presented in this paper will
help us to relatively simply build these compilers. In this way we aim to show that
GAL is both applicable to most adaptive engines as well as that it is generic. This
might pave the path in the future for general acceptance and standardization of a
engine-independent generic adaptation language.
Acknowledgements: This work was supported by the 7th Framework Program
European project GRAPPLE ('Generic Responsive Adaptive Personalized Learning
Environment').
2 Cf. http://www.grapple-project.org
23
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
References
[1] Owen Conlan, Vincent P. Wade, Catherine Bruen, and Mark Gargan. Multi-model,
Metadata Driven Approach to Adaptive Hypermedia Services for Personalized
eLearning. In Proceedings of the Second Adaptive Hypermedia and Adaptive Web-
Based Systems Conference (AH 2002), Malaga, Spain, May, 2002.
[2] Paul De Bra, David Smits, and Natalia Stash. The Design of AHA!. In Proceedings of
the 17th ACM Conference on Hypertext and Hypermedia (Hypertext 2006), Odense,
Denmark, August, 2006.
[3] Peter Brusilovsky, John Eklund, and Elmar W. Schwarz. Web-based Education for All:
A Tool for Development Adaptive Courseware. In Computer Networks and ISDN
Systems, 30(1-7), pp. 291-300, 1998.
[4] Geert-Jan Houben, Kees van der Sluijs, Peter Barna, Jeen Broekstra, Sven Casteleyn,
Zoltán Fiala, and Flavius Frasincar. Hera. Book chapter: Web Engineering: Modelling
and Implementing Web Applications, G. Rossi, O. Pastor, D. Schwabe, L. Olsina (Eds),
Chapter 10, pp. 263-301, 2008, Human-Computer Interaction Series, Springer.
[5] Peter Brusilovsky. Adaptive Hypermedia. In User Modeling and User-Adapted
Interaction, 11 (1-2), pp. 87-110, 2001.
[6] Gustavo Rossi and Daniel Schwabe. Modeling and Implementing Web Applications
with OOHDM. Book chapter: Web Engineering: Modelling and Implementing Web
Applications, G. Rossi, O. Pastor, D. Schwabe, L. Olsina (Eds), Chapter 6, pp. 109-155,
2008, Human-Computer Interaction Series, Springer.
[7] Marco Brambilla, Sara Comai, Piero Fraternali, and Maristella Matera. Designing Web
Applications with WebML and WebRatio. Book chapter: Web Engineering: Modelling
and Implementing Web Applications, G. Rossi, O. Pastor, D. Schwabe, L. Olsina (Eds),
Chapter 9, pp. 221-261, 2008, Human-Computer Interaction Series, Springer.
[8] Nora Koch , Alexander Knapp, Gefei Zhang, and Hubert Baumeister. Uml-Based Web
Engineering: An Approach Based on Standard. Book chapter: Web Engineering:
Modelling and Implementing Web Applications, Gustavo Rossi, Oscar Pastor, Daniel
Schwabe, and Luis Olsina (Eds), Chapter 7, pp. 157-191, 2008, Human-Computer
Interaction Series, Springer.
[9] Paul De Bra, Geert-Jan Houben, and Hongjing Wu. AHAM: A Dexter-based Reference
Model for Adaptive Hypermedia. In Proceedings of the 10th ACM Conference on
Hypertext and Hypermedia (Hypertext’99), Darmstadt, Germany, February, 1999.
[10] Nora Koch and Martin Wirsing. The Munich Reference Model for Adaptive
Hypermedia Applications. In Proceedings of the Second Adaptive Hypermedia and
Adaptive Web-Based Systems Conference (AH 2002), Malaga, Spain, May, 2002.
[11] Mario Cannataro and Andrea Pugliese. XAHM: An Adaptive Hypermedia Model
Based on XML. In Proceedings of the 14th International Conference on Software
Engineering and Knowledge Engineering (SEKE), Ischia, Italy, July, 2002.
[12] Frank G. Halasz and Mayer D. Schwartz. The Dexter Hypertext Reference Model. In
Communications of the ACM (CACM), 37(2), pp. 30-39, Febuary, 1994.
24
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Towards a Conceptual and Service-Based Adaptation
Model
Martin Harrigan and Vincent Wade
Department of Computer Science, Trinity College Dublin, Ireland
{martin.harrigan, vincent.wade}@cs.tcd.ie
Abstract. Current practice in adaptation modeling assumes that concepts and
relationships between concepts are the fundamental building blocks of any adaptive
course or adaptive application. This assumption underlies many of the mismatches
we nd between the syntax of an adaptation model and the semantics of the `real-
world' entity it is trying to model, e.g. procedural knowledge modeled as a single
concept and services or activities modeled as pockets of intelligent content. Further-
more, it results in adaptation models that are devoid of truly interactive services
with work ow and data ow between those services; it is impossible to capture the
semantics of a process-oriented application, e.g. activity-based learning in educa-
tion and Standard Operating Procedures (SOPs) in the workplace. To this end, we
describe a representation of a conceptual and service-based adaptation model. The
most signi cant departure from existing representations for adaptation models is
the rei cation of services. The goal is to allow for the adaptation of the process
itself and not just its constituent parts, e.g. an SOP can be adapted to the role or
job function of a user. This expressive power will address the mismatches identi ed
above and allow for activity-based and process-oriented adaptive applications.
1 Introduction
The cornerstone of an authoring tool-set for an adaptive course or adaptive application
is the adaptation model. It is the speci cation of the adaptive storyline or narrative [1]
that guides each user through a course or application. What makes the adaptation model
so di cult to author, is the very fact that there are so many dierent paths each user can
follow. A speci cation of an adaptation model serves two functions. Firstly, it determines
(or is determined by) what is expressible within an authoring tool-set [1, 2, 3, 4, 5].
Secondly, it hides the intricacies of the rule-based language or low-level instruction-set of
an adaptive engine, e.g. AHA! [2]. However, a problem with current adaptation models
is that they are unduly focused on concepts and relationships between concepts [6, 7, 8].
Procedural knowledge, interactive services and activities are di cult, if not impossible, to
model. Adaptation models require greater expressive power in order to adequately model
these possibilities.
To better illustrate this short-coming, consider adaptation models within an educa-
tional or learning environment. Activity is an important part of learning. For example,
This work was performed within the GRAPPLE Project. GRAPPLE (Generic Responsive
Adaptive Personalized Learning Environment) is an EU FP7 STREP project that aims to
deliver a Technology-Enhanced Learning (TEL) environment that guides learners through a
learning experience, automatically adapting to personal preferences, prior knowledge, skills
and competences, learning goals, and the personal or social context in which the learning
takes place. This functionality will be provided as a set of adaptive learning services that
will be integrated with existing Open Source and commercial Learning Management Systems
(LMSs).
25
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Active Learning [9] is a model of instruction that places the responsibility of learning
on learners through practical activity. In order to assimilate the learning material, the
learners must actively engage with it. Examples of active learning include class discussion
and `think-pair-share'. Situated Learning [10] states that learning is a function of activity,
context and the culture in which it takes place. It occurs as a result of social interaction,
e.g. through workshops, role-playing, eld trips, etc. Many other learning theories are
bound to the notion of an activity. At the same time, learners learn best when the learn-
ing experience oered to them meets their needs and stimulates their preferred modes of
learning [11]. When creating an adaptation model for such an environment, we should
consider not only adaptive content and adaptive navigation, but also adaptive learning
activities [12, 13]. We need to shift from learning objects and content that are `retrieved'
or `accessed' to learning activities that are `experienced'.
Our conceptual and service-based adaptation model is novel in the sense that it treats
services as rst-class citizens. Services and work ow between those services are explicitly
modeled. The goal is to provide for the adaptation of both concepts and services, i.e.
adaptive content, adaptive navigation, adaptive services, and adaptive work ow. This is
a fusion of the predominantly concept-centric models of adaptive hypermedia and the
service-centric models of work ow and process-oriented systems. In order to accomplish
this, we generalize the notion of a Conceptual Relationship Type (CRT) [14] to an Abstract
Relationship Type (ART) to cater for both.
This paper describes an adaptation model that explicitly provides for interactive ser-
vices and activities. It does not consider the theoretical or pedagogical concerns when
designing an actual adaptive course or adaptive application, nor does it detail a user
interface of an actual authoring tool-set. At the same time, we note that this work is
undertaken within a suitable context (see earlier footnote). The paper is organized as
follows. In Sect. 2 we provide de nitions for commonly used terms. In Sect. 3 we enu-
merate the broad requirements for a conceptual and service-based adaptation model. The
syntax and semantics of the abstract relationship type and adaptation model are detailed
in Sect. 4. This is followed by their usage in Sect. 5. We conclude and consider future
work in Sect. 6.
2 De nitions
This section establishes de nitions for commonly used terms in the paper.
A Resource Model (RM) [15] models all assets (concept instances and service instances)
that are available for use. These assets comprise text, images, sound, video, chat services,
email services, forum services, exercises, references, datasets, etc. The actual assets can
be contained in a closed-corpus repository or retrieved from an open-corpus repository,
such as the Web. However, every modeled asset must provide meta-data in the form
of a required set of controlled attributes. These attributes can specify, for instance, the
di culty of the content (e.g. introductory, intermediate, expert), the language, the media
format, etc. Service instances also need to expose their inputs and outputs.
A Domain Model (DM) [6, 15] comprises a Concept Domain Model (CDM) and a Ser-
vice Domain Model (SDM). A CDM models abstract concepts and relationships between
them. The actual concept instances are modeled in an RM. Concept spaces, taxonomies,
ontologies, and topic maps are all considered to be DMs. An SDM is an analogous model
for services. It models abstract services and relationships between them. The actual ser-
vice instances are modeled in an RM. Services can be domain-speci c in their very nature
whereas other services can be domain-independent but can be parameterized so that they
26
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
appear domain-speci c, e.g. `classDiscussion' can apply to any domain, but when the
discussion is parameterized with a particular topic, it becomes domain-speci c.
An Abstract Relationship Type (ART) is a relationship that can be instantiated be-
tween concepts, between services, or between concepts and services and provides for adap-
tive behavior. It is a generalization of a Conceptual Relationship Type (CRT) [14], in that
its parameters can be concepts or services. An authoring tool-set will provide a toolbox or
palette of commonly used ARTs. ARTs are distinct from the relationships in a DM; ARTs
provide for adaptive behavior, DM relationships do not. However, in some cases ARTs
can be derived from relationships in a DM, allowing DM relationships to be mapped to
particular ARTs. This is explored in Sect. 4.1 when discussing the derivedFrom element.
A conceptual and service-based Adaptation Model (AM) is an assembly of concepts and
services retrieved from a DM, with relationships between them, a work ow speci cation
guiding the execution of the services, and provisions for adaptive content, navigation,
service selection, work ow, and presentation. The relationships are instantiated ARTs
whose parameters are bound to the assembled concepts and services.
A User Model (UM) [6] is a store of attributes describing individual users and groups
of users; it permits software to adapt to their characteristics. It is sometimes useful to
distinguish between a UM schema how the UM is logically structured, and the actual
data stored in a particular UM. A simple overlay UM stores, for each concept (resp.
service) in a DM, a user's knowledge or familiarity with that concept (resp. service).
A strategy is a combination of ARTs that can only be instantiated within some prede-
ned pattern. It allows for the aggregation of ARTs in order to implement, for example,
quality control procedures, WebQuests, the Jigsaw learning technique, etc. The prede ned
pattern can permit a certain degree of customization, e.g. not all ARTs are mandatory.
This is explored in Sect. 4.1 when discussing the preConditions and postConditions
elements.
This proliferation of models does not lead to undue complexity [16]; in fact, it pro-
motes separation of concerns and allows, for example, DM experts to focus on DMs and
educational technologists and instructional designers to focus on ARTs and CRTs of a
pedagogical nature. In some cases, they may need to collaborate.
In the following sections, we refer to an example from the educational or learning
domain based on the student peer review process. This example is presented in detail in
Sect. 5
3 Requirements
In this section we enumerate some broad requirements for a conceptual and service-
based AM. These are based on recent interviews with potential users of an Adaptive
Learning System [17, 18] (an important application area for conceptual and service-based
adaptation models) and on previous experience with such models [12, 19, 1, 20, 21].
1. Concepts and services should be seamlessly integrated. Early approaches [21] provide
distributed, intelligent services that are embedded in concepts, that is, the concepts
contain the services. However, this does not support any form of information ow
between those services. The services amount to isolated, disconnected applets.
2. The representation should allow an author to create, manipulate, delete, and organize
all aspects of an AM. A canvas or workspace, into which an author can `drag-and-
drop' graphical representations of concepts, services and their relationships, supports
the inherently dynamic and creative process of designing an AM. The representation
should also include the spatial layout of an AM. Although this information does not
27
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
concern the semantics of an AM, it can be suggestive to an author of the directionality
and temporal sequence of the model.
3. The entities and relationships that an author has in mind when creating an AM (in-
troductory explanations, exercises, online discussions, prerequisites, roles etc.) should
be the same entities and relationships that they are controlling and manipulating in
the representation [22]. The model needs to operate at an appropriate level of ab-
straction. In practical terms, we would like an author to create, for example, an AM
that describes the student peer review process by assembling concepts and services
like `introductoryResource', `reviewResources', `discussion', and `writeReport' and in-
stantiating relationships like `prerequisite' and `followedBy'. The service `discussion'
may be realized in any number of ways depending on what service instances or re-
sources are available. However, when creating an AM, it is more appropriate for an
author to manipulate graphical artifacts entitled discussion. Similarly, an encap-
sulated relationship entitled `prerequisite' is more intuitive to an author than the
adaptive behavior (adaptive sequencing and presentation [23, 24]) it embodies.
4. Adaptive behavior should be abstracted and refactored [25] into reusable, exible re-
lationships. Concepts and services can be reused in many dierent AMs. The same
should be true for relationships like `prerequisite', `analogousTo', `conformsTo', `is-
SometimesFollowedBy', etc. This is a noticeable departure from existing representa-
tions and authoring tool-sets [7] that mix classical semantic relationships like `is-a'
and `has-a' with application relationships like `prerequisite' and `analogousTo' which
also embody adaptive behavior.
5. Practitioners appreciate the complexity and di culty in authoring an AM [17, 18].
This is the `price of adaptivity' [7]. However, they also seek an authoring tool-set that
can produce AMs without the intervention of specialists. To overcome this di culty,
the tool-set should provide as much advice and support as possible, e.g. during author-
time, the act of instantiating a relationship in an AM should only be allowed under
certain `terms-and-conditions'. This intelligence on the part of the tool-set is only
possible if the representation for each relationship includes such conditions. However,
the bene t is that the author can be advised at an early stage when something is
askew.
These requirements, namely the seamless integration of concepts and services (R1), the
`mix-and-match' paradigm (R2), an appropriate level of abstraction (R3), the abstraction
of reusable adaptive behavior (R4), and as much advice and support at author-time as
possible (R5) underlie many of the decisions in the following section.
4 Syntax and Semantics
In this section we present the syntax and semantics of the ART and the AM. ARTs
are instantiated in an AM so it is impossible to present one without the other. Fig. 1
summarizes their content. The ART schema comprises six elements described below.
The AM schema comprises ve elements also described below. An AM and a DM are
linked through the AM's entities element: it refers to concepts and services in the DM.
An AM and an ART are linked through the AM's relationships element: it contains
instantiations of ARTs.
4.1 The Abstract Relationship Type (ART)
ARTs are the glue that bind together the concepts and services in an AM. They are
also wrappers around the speci cation of adaptive behavior; they guide the author to the
28
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
ART Schema (art.xsd) AM Schema (am.xsd)
DM
header header
parameters entities
preConditions relationships
postConditions adaptiveBehavior
derivedFrom layout
adaptiveBehavior
Fig. 1. The ART and AM representations are described by XML Schema.
appropriate places in which to include this behavior. If more than one end point of an
ART is a service, then it also controls the work ow between those services, i.e. sequencing,
branching, merging, etc. By refactoring [25] the adaptive behavior into reusable ARTs, we
hope to improve the non-functional properties of an AM; namely its readability, maintain-
ability, and extendability. An authoring tool-set should provide an author with a toolbox
of commonly used ARTs. If an authoring tool-set is pedagogically-oriented, i.e. responsi-
ble for producing adaptive courses in a learning environment, then the ARTs should be
pedagogical in nature, e.g. `prerequisite', `analogous-to', `criticism-of', etc. However, these
are by no means the only type of ART we envision. For example, if an authoring tool-set
is responsible for producing Standard Operating Procedures (SOPs) for a workplace, then
the ARTs should cater for quality-control, e.g. `conforms-to', `requires-accreditation', etc.
The author may also need to tweak existing ARTs or create new ARTs from scratch.
Each ART comprises header, parameters, preConditions, postConditions, derived-
From, and adaptiveBehavior elements. These are speci ed using an XML Schema [26]
and are explained in the following subsections.
The header Element The header identi es an ART (identifier, author, name, de-
scription, keywords) and provides rudimentary support for versioning (majorVersion,
minorVersion) and permissions (permissions). identifier is a Universally Unique
IDenti er (UUID) [27] allowing each authoring tool-set to uniquely identify information
without signi cant central coordination. Authors are identi ed in the same way. name,
description and keywords are intended to help an author decide when and where an
ART is appropriate. The version number is separated into two elds, majorVersion and
minorVersion. The former is initialized to one and is incremented when the `interface' to
an ART changes, i.e. the number or types of parameters (speci ed below) are changed.
The latter is initialized to zero and is incremented for every other change in an ART. It is
reset to zero when majorVersion is incremented. An instantiated ART can be updated
to a new minor version automatically. However, an instantiated ART can be updated to a
new major version only through the intervention of an author. created and lastUpdated
29
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
are stored in Coordinated Universal Time (UTC) but can be translated to and from local
times by an authoring tool-set. The permissions element determines the access rights
to an ART. It follows a Unix-like mechanism. ARTs are managed using three distinct
classes: author, group, and world. Each can have read, write, and/or publish permis-
sions. There are, of course, many alternatives, including role-based access control [28]. It
is important to note that the model does not enforce these permissions but only allows
for their representation. It is left to an authoring tool-set or a local or remote persistence
service to enforce the rules.
The parameters Element An ART is instantiated between concepts and services
in an AM. The parameters element speci es the number and types of concepts and
services that it can be bound to. Each parameter is grouped under one of three distinct
classes: sources, targets, and undirected. The rst comprises parameters that are
`antecendents' of an ART; the second comprises parameters that are `consequents' of
an ART. For example, a `prerequisite' ART might describe entities X1 , X2 , . . . , Xs as
being prerequisites for entities Y1 , Y2 , . . . , Yt . X1 , X2 , . . . , Xs are classed as sources and
Y1 , Y2 , . . . , Yt are classed as targets. The third class, undirected, comprises parameters
that take part in an undirected ART. For example, a `similar-to' ART might describe an
entity X as being similar to an entity Y . If Y must also be similar to X then both X and
Y are classed as undirected.
Each parameter has its own identifier (UUID), name, type, minOccurs, and maxOc-
curs elements. type can have one of four values: concept, service, or either. They spec-
ify whether the parameter can be bound to a concept, service or either. The minOccurs
and maxOccurs elements aord several possibilities including mandatory (minOccurs =
1), optional (minOccurs = 0), and unbounded (minOccurs = 1 and maxOccurs = −1)
parameters. An ART must contain at least one parameter. An ART with exactly one
parameter can be considered a tag or loop. It adds adaptive behavior to single a entity.
The preConditions and postConditions Elements The preConditions and post-
Conditions elements are the `terms-and-conditions' of instantiating an ART in an AM.
The preConditions must hold before an ART is instantiated and the postConditions
must hold after. All conditions are structural and can be checked at author-time. They
provide an authoring tool-set with some intelligence to guide an author. We enumer-
ate and describe the conditions which can appear within either the preConditions or
postConditions tags:
1. minDegree: This is the minimum number of relationships that an entity bound to a
parameter of an ART can take part in.
2. maxDegree: This is the maximum number of relationships that an entity bound to a
parameter of an ART can take part in.
3. directedCycle: This determines whether instantiations of an ART can induce a di-
rected cycle. For example, it should not be possible for instantiations of a `prerequisite'
ART to induce a directed cycle: X is a prerequisite for Y , Y is a prerequisite for Z
and Z is a prerequisite for X .
4. isParameterOfART: This constrains an entity bound to a parameter of an ART into
being bound to a parameter of some other ART. This forces certain ARTs to be
instantiated in sequences or in combination with other ARTs, thus providing an im-
plementation of our earlier de nition of a strategy (see Sect. 2).
30
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
The derivedFrom Element An author creates an AM by assembling collections of
concepts and services and instantiating ARTs between them. An authoring tool-set should
assist the author in this endeavor. Consider the case where an author copies two entities, X
and Y , from a DM into an AM and there already exists a DM relationship between them,
e.g. X `is-a' Y . It may sometimes be desirable and expedient for ARTs to be instantiated
automatically or semi-automatically (through a dialogue with the author) in response
to this, e.g. Y is a prerequisite of X can be derived from the fact that X `is-a' Y . The
derivations are speci ed within the derivedFrom element. This approach dierentiates
between user-agnostic DM relationships that are present in concept spaces, taxonomies,
ontologies, and topic maps and ARTs that have adaptive behavior and references to
UM attributes associated with them while allowing the latter to be automatically derived
from the former. This allows, for example, the automatic derivation of adaptive navigation
structures, e.g. concept-based hyperspaces [7].
The adaptiveBehavior Element The nal element, adaptiveBehavior, speci es the
adaptive behavior of an ART using an appropriate adaptation language [29, 30] within a
single CDATA block. This language should be independent from the DM, adaptive engine,
and target platform. It can reference the parameters from the parameters element above
and can query and update the attributes of the UM. At publish-time (when the AM is
translated to the low-level instruction-set of an adaptive engine), references to parameters
are substituted with the identi ers of the entities they are bound to.
4.2 The Conceptual and Service-Based Adaptation Model (AM)
The AM is a model into which concepts and services are assembled and ARTs are instan-
tiated. It is a mapping between the `knowledge space' and what is eventually presented
to a user [7]. An author creates an AM in a declarative fashion; he or she declares the
high-level structure of an AM. The entities and relationships that the author has in mind
when preparing an AM are the same artifacts that he or she is controlling and manipu-
lating in the workspace, e.g. an introductory explanation, exercise, online discussion, etc.
The adaptive behavior of each ART and an AM as a whole (also speci ed in an adapta-
tion language) provide an imperative list of actions that realize the author's intent. Each
AM comprises header, entities, relationships, adaptiveBehavior, and layout ele-
ments. These are speci ed using an XML Schema [26] and are explained in the following
subsections.
The header Element The header element is identical to the header of an ART; it iden-
ti es an AM (identifier, author, name, description, keywords) and provides rudimen-
tary support for versioning (majorVersion, minorVersion) and permissions (permissions).
The entities Element The building blocks of an AM are its entities. Each entity
can be either a concept or a service from a DM and is identi ed through an identifier.
It references the identifier and version of the concept or service (if they exist). Each
entity also includes a list of controlledAttributes along with values. These place
further restrictions on the actual concept or service instance that can be retrieved for
each entity when an AM is published. For example, suppose an author includes a service
from a DM entitled `discussion'. However, suppose also that there are a number of dierent
service instances or implementations that oer this functionality but vary in form. For
example, in one instance, an instant-messaging portlet is provided, in another, a discussion
31
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
forum or bulletin board system is used. One standardized possibility for the controlled
list of attributes the Dublin Core [31] elements. In the case of `discussion', an attribute
named `duration' with a value of `short' would restrict the actual service instances that
can be retrieved for this entity to those that persist for a short period of time.
The relationships Element The relationships element is the container for in-
stantiated ARTs. Each instantiated ART is identi ed through an identifier. It also
identifier and version of an ART it is an instantiation of. It maps the
references the
parameters of an ART to the entitys of an AM. This mapping determines the entities
that the instantiated ART is gluing together. For example, suppose a `conforms-to' ART
has two parameters: a service X (source parameter) and a concept Y (target parameter).
When an author instantiates this ART between, say, an interactive `generalLedger' service
and the `doubleEntryBookkeeping' concept, X is bound to `generalLedger' and Y is bound
to `doubleEntryBookkeeping'. This is identical to the binding of arguments to function
parameters in programming languages. An authoring tool-set can ensure at author-time
that the type, minOccurs and maxOccurs children of each parameter element of each
instantiated ART are satis ed. Furthermore, it can also ensure at author-time that the
preConditions and postConditions of each instantiated ART are satis ed. An instan-
tiated ART must be bound to at least one entity. An instantiated ART that is bound
to exactly one entity can be considered a tag or loop. It adds adaptive behavior to a
single entity.
The adaptiveBehavior Element The adaptiveBehavior element speci es the adap-
tive behavior of an AM using an appropriate adaptation language [29, 30] within a single
CDATA block. This behavior is independent of any of the individually instantiated ARTs.
It can reference the individual entity and relationship elements above and can query
and update the attributes of the UM. For example, it could save and retrieve the last
known position of a user within the structure of an AM or it could change the role or
quali cations of a user at the appropriate time.
The layout Element Finally, the layout element provides a graphical representation
of an AM. This representation is based on a graph model. A graph is a mathematical
structure typically used to model the relationships between objects. It consists of nodes
or vertices linked together by (possibly directed, weighted ) edges. A graph can be de ned
by a list of vertices and edges, by using a matrix structure or simply by a drawing of
the graph. A drawing of a graph is a visual representation of its vertices and edges. We
describe one such representation. A polygonal or circular shape depicts a vertex with an
optional label printed inside or close to the shape. An edge is depicted by a polyline or
curve which connects the shapes and may also have an optional label. If an edge has
an associated direction it is decorated with an arrow to indicate this direction. A `good'
drawing of a graph not only de nes the graph but also eectively aids its comprehension
by authors. Our graph drawings are also subject to constraints [32] that re ect the domain
of AMs, e.g. their layout can be suggestive of the directionality and temporal sequence of
the model. Graphs provide a uniform interface over heterogeneous models with standard
graphical operations and easily-understood semantics. The same interface can be used
for both creating and manipulating existing AMs. Indeed, we expect high-quality AMs to
evolve rather than be completely designed from the ground up. Therefore, the interface
must cater for both creation and maintenance.
A vertex can represent either a concept or a service. An edge represents an ART. Any
subgraph can be contracted to a single vertex. It can be expanded again as necessary.
32
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
An entire graph represents an AM. An author creates an AM by dragging vertices and
edges from a palette and adding them to a graph. For example, adding a vertex that
represents some concept and linking it with an edge to some service indicates that the
concept and the service are related. The service might be a realization of the concept or
it might conform to the principles of the concept, etc. The type of relationship will be
indicated by the type and labeling of the edge. Vertices and edges can also be removed.
The actual drawing or layout of a graph does not concern the semantics of an AM. It
is purely an aid for the author when comprehending the structure and contents of an
AM. The interface enforces constraints during author-time. For example, when dragging
an ART from a palette and adding it to a graph, the edge can only be added between
vertices whose type matches those of the ART's parameters.
We use GraphML [33] to store our layout data. Our AM schema imports the GraphML
schema and the contents of the layout element adhere to this schema. GraphML can also
be extended using either attributes to attach scalar values or key/data pairs to attach
structured data to a graph. This reduces the burden on us, allowing us to focus solely on
the representation of an AM and not on the graphical and topological aspects.
5 Example Usage
The LADiE project [34] has developed a broad set of use case scenarios for activity-based
e-Learning. One such scenario requires students to review a set of resources relating to a
speci c topic. This review is followed by a discussion on the topic, which is guided by the
teacher. The students then write and submit a report based on their discussion. There is
also the possibility that a student can re-examine the resources, and discuss the problem
while writing the report at the same time. The list of steps is:
1. Teacher briefs students on the activity.
2. Students log into the system and access the resources.
3. Students discuss the problem.
4. Students write report.
5. Students submit report.
6. System noti es teacher that report has been submitted.
We wish to adapt both the content and the work ow of these activities to the needs
of the students. The content can be adapted based on various adaptive axes such as the
students' prior knowledge. In addition to this, the services can be tailored to the needs
of the students as well as to their context. For example, discussion between groups of
students can be supported by various dierent services. A bulletin board service might
be appropriate if the activity is expected to run over a long period of time while a chat
room service might be more appropriate for a relatively short activity where all of the
students are online. Similarly, the writing and submission tasks can employ a choice of
services.
For the purpose of this example, we assume that the topic is Digital Rights Manage-
ment (DRM) and that the author has access to a DM containing concepts like `DRM',
`DRMTechnologies', and `DRMLegislation' and services like `reviewResources', `discus-
sion', `writeReport', and `submitReport'. The author drags each of these entities into an
AM. He instantiates a `prerequisite' ART between `DRM' and `DRMTechnologies' and
between `DRM' and `DRMLegislation'. He instantiates a `isLegalIssue' ART whose only
parameter is `DRMLegislation'. This ensures that the `DRMLegislation' concept is only
presented to the class if they have an interest in law. The author instantiates an `and-
Split' ART between `DRMTechnologies' and the services `reviewResources', `discussion'
33
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
DRM review
Technologies Resources
prereq. andSplit
prereq. discussion
DRM
start end
prereq. DRM
Legislation submit
write
isLegalIssue Report Report
Fig. 2. The student peer review process.
and `writeReport'. This indicates that once a student has studied the `DRMTechnologies'
concept he or she can perform the next three services in parallel, switching between them
as needed. These may be presented to the user as three separate windows or portlets.
Of course, it is altogether possible that an instantiation of an `andSplit' ART is not only
distinguished by its label but also by a unique graphical depiction one that is similar
to `split' constructs in visual work ow languages. Finally, the author instantiates a `se-
quence' ART between the `writeReport' and the `submitReport' services. The outcome is
illustrated in Fig 2.
6 Conclusions and Future Work
We have presented the basic ingredients of an AM that supports the adaptive selection, se-
quencing and presentation of both concepts and services. By putting services on an equal
footing with concepts, we allow for adaptive service selection and adaptive sequencing of
the services themselves. We have generalized the notion of CRTs [14] to cater for these
new possibilities. Within the context of the GRAPPLE Project (see earlier footnote), we
are developing a graph-based authoring tool-set that will be based on this AM. The tool-
set will comprise a Rich Internet Application (RIA) that will enable authors, in particular
teachers, educational technologists and instructional designers, to compose AMs repre-
senting adaptive courses and adaptive procedural simulations. Server-side functionality
will enable translation of this AM to the rule-based languages or low-level instruction-sets
of an adaptive engine, e.g. AHA! [2].
There are many possible extensions to the AM. For example, some DMs use a frame-
like knowledge representation, i.e. they model the internal structure of each concept or
service. Instead of assembling entire concepts or services in an AM, an author may want
to mix and match parts of dierent concepts and services. Also, we believe that the
analogy between ARTs and functions in programming languages, mentioned in Sect. 4.2,
is particularly apt. We are considering the bene ts of inheritance and overloading when
applied to ARTs.
References
[1] Dagger, D., Wade, V., Conlan, O.: Personalisation for All: Making Adaptive Course
Composition Easy. Educational Technology and Society 8(3) (2005) 925
34
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
[2] De Bra, P., Smits, D., Stash, N.: Creating and Delivering Adaptive Courses with
st
AHA! In Nejdl, W., Tochtermann, K., eds.: Proceedings of the 1 European Con-
ference on Technology Enhanced Learning (EC-TEL'06), Springer (2006) 2133
[3] Specht, M., Krav£ík, M., Klemke, R., Pesin, L., Hüttenhain, R.: Adaptive learning
nd
environment for teaching and learning in winds. In: Proceedings of the 2 In-
ternational Conference on Adaptive Hypermedia and Adaptive Web-Based Systems
(AH'02), Springer (2002) 572575
[4] Krav£ík, M., Specht, M., Oppermann, R.: Evaluation of WINDS Authoring Environ-
rd
ment. In: Proceedings of the 3 International Conference on Adaptive Hypermedia
and Adaptive Web-Based Systems (AH'04), Springer (2004) 166175
[5] Cristea, A., de Mooij, A.: Adaptive Course Authoring: My Online Teacher. In:
th
Proceedings of the 10 International Conference on Telecommunications (ICT'03).
(2003) 17621769
[6] De Bra, P., Houben, G., Wu, H.: AHAM: A Dexter-Based Reference Model for
th
Adaptive Hypermedia. In: Proceedings of the 10 ACM Conference on Hypertext
and Hypermedia (HYPERTEXT'99), ACM (1999) 147156
[7] Brusilovsky, P.: Developing Adaptive Educational Hypermedia Systems: From De-
sign Models to Authoring Tools. In Murray, T., Blessing, S., Ainsworth, S., eds.:
Authoring Tools for Advanced Technology Learning Environments. Kluwer Aca-
demic Publishers (2003) 377409
[8] Cristea, A., Smits, D., De Bra, P.: Towards a Generic Adaptive Hypermedia Plat-
form: A Conversion Case Study. Journal of Digital Information 8(3) (2007)
[9] Bonwell, C., Eison, J.: Active Learning: Creating Excitement in the Classroom.
AEHE-ERIC Higher Education Report 1, Washington, D.C. (1991)
st
[10] Lave, J., Wenger, E.: Situated Learning: Legitimate Peripheral Participation. 1
edn. Cambridge University Press (1991)
[11] Conlan, O., Hockemeyer, C., Wade, V., Albert, D., Gargan, M.: An Architecture
for Integrating Adaptive Hypermedia Services with Open Learning Environments.
In Barker, P., Rebelsky, S., eds.: Proceedings of World Conference on Educational
Multimedia, Hypermedia and Telecommunications (ED-MEDIA'02), AACE (2002)
344350
[12] Conlan, O., O'Keee, I., Brady, A., Wade, V.: Principles for Designing Activity-
Based Personalized eLearning. In Spector, J., Sampson, D., Okamoto, T., Kinshuk,
th
Cerri, S., Ueno, M., Kashihara, A., eds.: Proceedings of the 7 IEEE International
Conference on Advanced Learning Technologies (ICALT'07), IEEE Computer Society
(2007) 642644
[13] O' Keee, I., Brady, A., Conlan, O., Wade, V.: Just-In-Time Generation of Peda-
gogically Sound, Context Sensitive Personalized Learning Experiences. International
Journal on E-Learning 5(1) (2006) 113127
[14] De Bra, P., Aerts, A., Rousseau, B.: Concept Relationship Types for AHA! 2.0.
In Richards, G., ed.: Proceedings of World Conference on E-Learning in Corporate,
Government, Healthcare, and Higher Education (E-Learn'02), AACE (2002) 1386
1389
[15] Conlan, O., Wade, V., Bruen, C., Gargan, M.: Multi-Model, Metadata Driven Ap-
proach to Adaptive Hypermedia Services for Personalized eLearning. In De Bra, P.,
nd
Brusilovsky, P., Conejo, R., eds.: Proceedings of the 2 International Conference on
Adaptive Hypermedia and Adaptive Web-Based Systems (AH'02), Springer (2002)
100111
[16] Conlan, O., Wade, V.: Evaluation of APeLS - An Adaptive eLearning Service Based
on the Multi-Model, Metadata-Driven Approach. In De Bra, P., Nejdl, W., eds.: Pro-
35
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
ceedings of the 3rd International Conference on Adaptive Hypermedia and Adaptive
Web-Based Systems (AH'04), Springer (2004) 291295
[17] Harrigan, M., Krav£ík, M., Steiner, C., Wade, V.: What Do Academic Users Want
from an Adaptive Learning System? Technical Report, Trinity College Dublin (2009)
https://www.cs.tcd.ie/publications/tech-reports/reports.09/TCD-CS-2009-06.pdf.
[18] Harrigan, M., Krav£ík, M., Steiner, C., Wade, V.: What Do Academic Users Really
Want from an Adaptive Learning System? In: Proceedings of the 17th International
Conference on User Modeling, Adaptation, and Personalization (UMAP'09) (to ap-
pear), Springer (2009)
[19] O'Keee, I., Conlan, O., Wade, V.: A Uni ed Approach to Adaptive Hypermedia
Personalisation and Adaptive Service Composition. In Wade, V., Ashman, H., Smyth,
B., eds.: Proceedings of the 4th International Conference on Adaptive Hypermedia
and Adaptive Web-Based Systems (AH'06), Springer (2006) 303307
[20] Wilson, S., Blinco, K., Rehak, D.: An e-Learning Framework: A Summary. In:
Proceedings of the Advancing Learning Technology Interoperability Lab Conference
(ALT-I-LAB'04). (2004)
[21] Brusilovsky, P.: KnowledgeTree: A Distributed Architecture for Adaptive E-
Learning. In Feldman, S., Uretsky, M., Najork, M., Wills, C., eds.: Proceedings
of the 13th International Conference on World Wide Web Alternate Track Papers
and Posters (WWW'04), ACM (2004) 104113
[22] Rosch, E.: Natural Categories. Cognitive Psychology 4(3) (1973) 328350
[23] Brusilovsky, P.: Methods and Techniques of Adaptive Hypermedia. User Modeling
and User-Adapted Interaction 6(23) (1996) 87129
[24] Brusilovsky, P.: Adaptive Hypermedia. User Modeling and User Adapted Interaction
11(12) (2001) 87110
[25] Fowler, M., Beck, K., Brant, J., Opdyke, W., Roberts, D.: Refactoring: Improving
the Design of Existing Code. Addison-Wesley (1999)
[26] W3C: XML Schema http://www.w3.org/XML/Schema.
[27] Leach, P., Mealling, M., Salz, R.: A Universally Unique IDenti er (UUID) URN
Namespace. Technical Report RFC 4122, The Internet Engineering Task Force
(IETF) (2005) http://tools.ietf.org/html/rfc4122.
[28] Sandhu, R., Coyne, E., Feinstein, H., Youman, C.: Role-Based Access Control Mod-
els. IEEE Computer 29(2) (1996) 3847
[29] Hendrix, M., De Bra, P., Pechenizkiy, M., Smits, D., Cristea, A.: De ning Adapta-
tion in a Generic Multi Layer Model: CAM: The GRAPPLE Conceptual Adaptation
Model. In Dillenbourg, P., Specht, M., eds.: Proceedings of the 3rd European Con-
ference on Technology Enhanced Learning (EC-TEL'08), Springer (2008) 132143
[30] Stash, N., Cristea, A., De Bra, P.: Adaptation Languages as Vehicles of Explicit In-
telligence in Adaptive Hypermedia. International Journal of Continuing Engineering
Education and Life-Long Learning 17(45) (2007) 319336
[31] The Dublin Core Metadata Initiative: http://www.dublincore.org.
[32] Tamassia, R.: Constraints in Graph Drawing Algorithms. Constraints 3(1) (1998)
87120
[33] Brandes, U., Eiglsperger, M., Herman, I., Himsolt, M., Marshall, S.: GraphML
Progress Report. In Mutzel, P., Jünger, M., Leipert, S., eds.: Proceedings of the
9th International Symposium on Graph Drawing (GD'01), Springer (2001) 501512
[34] JISC: Learning Activity Design in Education: LADiE. Technical report, The Joint
Information Systems Committee (JISC) (2006) http://www.jisc.ac.uk/publications.
36
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Non-Invasive Adaptation Service for Web-based Content
Management Systems
Kevin Koidl, Owen Conlan, Vincent Wade
Centre for Next Generation Localisation and Knowledge and Data Engineering Group, Trinity
College Dublin, Ireland
{Kevin.Koidl, Owen.Conlan, Vincent.Wade}@cs.tcd.ie
Abstract. Most Adaptive Hypermedia Systems today focus on providing an
adaptive portal or presentation/application through which adaptive retrieved content
is delivered. Moreover the content used by such adaptive systems tends to be
handcrafted for adaptivity, i.e. from closed corpus repositories. If adaptive
hypermedia is to become more mainstream we need the ability to embed adaptive
information retrieval and composition techniques within existing Web-based
Content Management Systems (WCMS) e.g. Wiki, Drupal. However the effort and
expense in fundamentally re-engineering such WCMS or developing completely
new adaptive WCMS, is very high. This research explores the architectural and
technical issues involved in providing a third party adaptive service which is more
easily plugged into existing WCMS. The advantage of this approach is that it
doesn’t break the current browsing paradigm of freely navigating across different
independent web sites on the web. In order to address this challenge we introduce a
third party Adaptive Service that enables a unified cross-website personalized
experience by discretely interfacing with separate independent WCMS. Thus the
Adaptive Service strives to personalize the users experience when accessing each
WCMS in a non-invasive manner by not adversely interfering with the web sites
overall look and feel, content and functionality without losing the web sites identity
and fundamental experience. This paper describes the design and an initial use case
supported implementation example of this Adaptive Service. It also provides a
survey that assesses the feasibility of the services integration with leading WCMS.
Keywords: Open Corpus, Adaptive Hypermedia, Web-based Content
Management Systems (WCMS), Adaptive Hypermedia Strategies
1 Introduction
Although Adaptive Hypermedia Systems (AHS) have matured, they may still be seen
as a niche application mostly with a manually managed closed corpus that is adapted
to a well known user group. Furthermore the adaptive logic driving the adaptive
process needs to be closely related to the data models and the content. This close
relationship mostly results in limitations in the re-usability and interoperability of the
AHS, also known as the “Open Corpus Problem” in Adaptive Hypermedia [2].
37
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Recently more flexible AHS architectures have been introduced addressing the
problem of re-usability and interoperability. E.g. by providing a distributed server
architecture [1] or flexible rule engines facilitating the adaptive logic [4].
Nevertheless most AHS still tend to provide a central AHS portal restricting the user’s
flexibility; thus isolating the adaptive experience. This paper introduces an approach
using a flexible AHS architecture and providing flexibility to the user.
The goal of this approach is to provide open corpus adaptivity by personalizing the
browsing experience over several individual content hosting systems known as Web-
based Content Management Systems (WCMS). To achieve this we introduce a third-
party Adaptive Service discretely interfacing with the individual WCMS. The main
advantage of this approach is that the adaptivity is instrumented by the WCMS and
not by a central AHS portal. By bringing the adaptivity to the WCMS, the user can
maintain the current browsing paradigm by freely navigating on the web and, at the
same time, benefiting of personalized content. For this the Adaptive Service provides
the individual WCMS with non-intrusive adaptive recommendations reflecting the
overall intent/interest of the user. The unified and personalized browsing experience
across different WCMS is defined as adaptive flow.
In order to illustrate the functionality of the introduced third-party Adaptive Service a
use case is provided in section 4. This use case describes the individual steps in which
a user can be assisted on the web by the introduced third-party Adaptive Service.
Based on the use case one particular implementation example is also given. This
example includes a query interception and augmentation by the third-party Adaptive
Service connected to a WCMS. The implementation example is followed by a
description of the overall architecture.
Motivating the use case, a survey of two prominent WCMS Drupal and Wikipedia’s
implementation platform MediaWiki is provided. The survey focuses on the
suitability of WCMS for adaptivity. Furthermore a state of the art in discussing recent
developments in flexible service driven AHS is also provided.
2 Adaptive Hypermedia and third-party services integration
In order to develop a third-party Adaptive Service, which integrates with different
WCMS, three main challenges need to be addressed: (1) the identification and
implementation of necessary adaptive features in WCMS, (2) the development of
adaptive logic driving the personalization process across several independent WCMS
and (3) providing a user model unifying the browsing experience across the different
WCMS. The second and third challenge is addressed in the following state of the art
by discussing current AHS and user modelling developments. However the first and
most difficult challenge is addressed in the two following separate sections three and
four.
For an AHS to allow more flexible adaptation across different WCMS the possibility
of separating the adaptive logic from the content is essential. Recently several
38
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
research groups are driving their AHS towards more flexible AHS architectures. A
subset of the numerous examples discussed in the literature is: KnowledgeTree [1],
APeLS [4], MEDEA [13] and AHA! [6]. E.g. KnowledgeTree implements an AHS by
providing a community of distributed servers to clearly separate concerns. This is
done by distributing different functions to designated servers compared with one AHS
bundling all functionalities together. For this KnowledgeTree provides four types of
servers: learning portals, activity servers, value-added services, and student model
servers [1]. Although the communications protocols between the different distributed
servers are based on a simple HTTP GET request and not on Web Service protocols
such as SOAP, KnowledgeTree provides a good example of distributed AHS
integration relevant to this research.
APeLS, as another example, also provides a distributed architecture, although by
using separate adaptive services not servers. Furthermore APeLS enables Web
Service based communication between the different AHS services. The individual
AHS services are (a) the adaptive hypermedia service providing the content and (b)
the learning environment. The later is used to track the learner, based on the tutor’s
guidance in the form of learner profiles, assessment information and pedagogical
constraints. The result integrates both services and is displayed in the client’s
browser. Furthermore APeLS allows the flexible design of adaptive logic based on
pluggable rule engines managing different narratives driving the adaptivity [5]. In
addition to the usage of Web Service communication the multi model approach of
APeLS is relevant to this research. Nevertheless both KnowledgeTree and APeLS
focus on closed corpus and not apply adaptation across multiple independent services
in order to include open corpus in the adaptation process.
In the following the integration of user models within a third-party Adaptive Service
is discussed. The main challenge is to provide a modelling approach that reflects a
unified browsing experience over several different WCMS without the need to model
separate user models for each WCMS. For this a distributed user modelling service
unifying the different modelling parameters of the WCMS is necessary. For example
Personis [8] provides such a distributed user model approach designed to provide a
unified user model of several different systems. An additional distinctive feature of
Personis is user model scrutiny, ensuring the user is involved in all user model related
decisions. The architecture is based on a XML-RPC interface allowing third party
service integration. A similar approach, centralizing the user model, is taken by
CUMULATE [3]. Nevertheless Personis and CUMULATE lack flexibility due to the
unified storage of user models in a centralized repository. A more flexible approach is
followed by FUMES [15] providing a decentralized mapping framework to support
the exchange of heterogeneous user models without the need of a central repository.
In relation to the introduced third-party Adaptive Service FUMES provides a
possibility of retrieving a single user model based on user information collected in
several different WCMS.
39
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
3 WCMS survey for compatibility to support modular based
Adaptive Service access
This section is based on a survey investigating the integration of third party adaptive
services in Web-based Content Management Systems (WCMS). The following is only
a brief extract of the entire survey introducing the most important conclusions for this
research.
Taking a broad view on WCMS shows that this type of system refers to a whole range
of different applications and functionalities with the main commonality of providing
effective and accessible tools for publishing and organising web-based content.
Goodwin and Vidgen define a WCMS as:
“ [...] an organizational process, aided by software tools, for the management of
heterogeneous content on the web, encompassing a life cycle that runs from creation
to destruction” [14]
The term WCMS mostly refers to open source based Content Management System
rather than to commercial systems which are referred to as Enterprise Content
Management Systems (ECM). Prominent examples for WMCS are MediaWiki,
Drupal and WordPress. Beside these systems numerous WCMS have appeared and
have become an enormously popular application domain in day to day Internet
activities.
The integration of adaptive functionalities in WCMS pose a new set of challenges
towards the adaptive process with the following as the most significant:
x Any adaptive intervention has to maintain the entire look and feel i.e.
branding of the WCMS.
x All internal policies regarding user rights, especially content-related rights,
need to be obeyed by any adaptive intervention.
x The WCMS has to provide API or Web Service interfaces to enable third
party Adaptive Service intervention.
x The WCMS needs to be extendible/pluggable in order to handle adaptive
interventions.
x Semantic web functionalities have to be available within the WCMS, e.g. via
a module based extension to the core platform.
To assess and tackle these challenges, two specific WCMS were examined,
MediaWiki [9] well known as the basic WCMS used for Wikipedia and Drupal [7]
known as one of the most flexible WCMS based on its flexible pluggable module
architecture. Both systems provide a wide range of possibilities and are supported by
a large and active developer group.
The architecture of MediaWiki is simpler than Drupals, but it is not as flexible. This is
due to the fact that Drupal is based purely on a module based pluggable architecture.
40
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
However MediaWikis core strength lies in the management of content and not in the
extensibility of the platform. Nevertheless extensions are possible, e.g. the extensions
feature is based on simple scripts for the adding of different plugin types like Adobe
Flash, Video streaming, RSS feeds, ratings and API based third party accessibility. It
also has to be noted that recently more enhanced extensions were introduced
especially for the adding of semantic structures and relationships within the different
MediaWiki implementation [10].
The WCMS Drupal on the other hand is based on a flexible module based pluggable
framework also referred to as “Content Management Framework” [7]. Drupal does
not specialise on one specific type of content, like MediaWiki which focuses on
encyclopaedia based content or Wordpress concentrating on blog based content, but it
provides an extendible core implementation that can plug different modules
depending on the application area. This high level of flexibility and abstraction comes
with the cost that developers need to have good knowledge of the core architecture in
order to extend it. Like MediaWiki, Drupal also provides a module to enable semantic
annotations [11].
However it is essential to explore the extensibility of WCMS for it to engage with a
third-party Adaptive Service and to provide the ability to use the adaptive
interventions send by a third-party Adaptive Service. Currently both discussed
WCMS provide the possibility to communicate with a third-party Adaptive Service.
Nevertheless both need to be extended to cater for effective adaptivity from within.
Currently it is not possible to take any WCMS deployment and apply adaptivity
simply by using API function calls.
Fortunately the engineering of a WCMS is not a difficult task and especially in the
case of MediaWiki and Drupal extensibility is possible without major changes to the
WCMS architecture. E.g. MediaWiki API provides a powerful interface for fast and
high level access to all data within the database. Functions include user login, content
uploads and updates. In addition to the API MediaWiki provides specific extension
points for the extension of its deployment. These extensions can be plugged into the
core implementation at any time and do not trigger any re-deployment. The following
extensions can be seen as relevant for enabling adaptivity in MediaWiki: “Hooks” to
react to user actions, displaying “special pages” and “skins” allowing changes in the
look and feel of MediaWiki.
Extending the main Drupal core on the other hand implies the extension with specific
Drupal modules. These modules are simple to design, plug and unplug. From within
the modules several functionalities to control the information flow from the database
to the Front End are provided. Following events are useful for the “hooking” of
adaptive interventions into Drupal: Content/Node creation, deletion and viewing, as
well as user login/logout and user account/profile updates. Both WCMS, MediaWiki
and Drupal therefore provide a good base for further development towards more
flexible and distributed adaptivity.
41
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Besides applying extensions to the individual WCMS an alternative approach is
possible. This approach is based on the fact that most interactions between user and
WCMS are based on the usage of a browser. Furthermore current browser
technologies allow the integration of extension/plug-in which can be used to
manipulate, augment or redirect the data before being displayed to the user. In relation
to this research an interesting example is the “Smarter Wikipedia” Firefox plug-in,
which adds a “related articles” box to MediaWiki’s Wikipedia implementation [12].
This kind of browser central development presents an alternative approach which
avoids the current need to extend WCMS, but may lead to constant updates due to
changes in the underlying WCMS. Nevertheless a purely browser focused
implementation is currently not part of the approach introduced in this paper.
In the following a use case is illustrated discussing the usage of the third-party
Adaptive Service on WCMS.
4 Use Case
This use case illustrates the usage of the third-party Adaptive service providing a
unified adaptive experience over several independent WCMS. As mentioned above
this unified experience is defined as adaptive flow. It’s main purpose is to retain a
unified personalized information space for the user. To achieve this each of the
WCMS communicates with a third-party Adaptive Service. As the user navigates, the
Adaptive Service gains knowledge about their browsing over time. Thus, the
Adaptive Service can provide improved non-intrusive adaptive recommendations to
the WCMS. Figure 1 illustrates a specific scenario.
42
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
User Content
Model Model
Strategy
Model
Figure 1 illustration of the overall adaptive approach indicating an adaptive flow over several
different WCMS
1. User John is interested in installing the Debian GNU/Linux based Ubuntu
operating system, but before he makes his final decision he wants to gather
information about the installation process. For this he navigates to the Drupal
based Ubuntu homepage. John’s Adaptive Service is active and will provide
a more personal browsing experience.
2. After navigating to the Ubuntu homepage John states the explicit part of his
interest in the search field. He uses the term “install Ubuntu”.
3. The search module of the Drupal based Ubuntu homepage informs the third-
party Adaptive Service about John’s query. The Adaptive Service registers
the query and cannot find any previous interest related to this query.
Therefore the Adaptive Service initialises a new “adaptation flow” session
prompting the Adaptive Service to wait for more evidence coming from
John’s interaction with the Ubuntu homepage.
4. After stating the query John receives the result list from the Ubuntu
homepage without any adaptive interventions. He starts clicking on different
results from the original result list.
5. John’s interaction with the result list is registered by the Adaptive Service.
At this point the Adaptive Service remains in a non-adaptive state identifying
John as being in an ‘orientation’ phase.
6. John believes he has enough high level information and leaves the Ubuntu
homepage. Now he navigates to the MediaWiki implementation “wikiHow”.
43
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
He wants to receive more in depth information about the installation process
and hopes to find it at this point.
7. The Adaptive Service is informed by “wikiHow” and registers John’s access
to the MediaWiki based page. John uses this page frequently and knows that
the Adaptive Service is interacting with the WikiMedia based WCMS. After
the Adaptive Service receives the information that John is navigating to the
new WCMS the Adaptive Service sends an extended query to the
“wikiHow” page. John is now presented with a personalized result list based
on his previous browsing experience on the Ubuntu Homepage, instead of
seeing the main homepage in which John would have had to reissue his
query.
8. After interacting with the personalized search result provided by the
“wikiHow” webpage, John decides to navigate to the WordPress based
blogging site “Ubuntu blog”.
9. The Adaptive Service now maintains a well informed stream of experience
from John’s previous browsing pattern and is able to negotiate the most
appropriate blog entries for John.
10. John believes he is well informed and decides to install Ubuntu.
The most essential part of the illustration in figure 1 is indicated with the diagonal
arrows ranging over the different WCMS. It indicates the adaptive flow which can be
seen as a development towards a more personalized browsing experience.
Furthermore it is important to note that the illustrated open corpus adaptive scenario is
controlled principally by the user. The Adaptive Service only provides adaptive
recommendations which then can be used by the WCMS during their interaction. The
use of the Adaptive Service allows different WCMS to share the latent aspects of the
user’s preferences and intent. These are typically lost as the user navigates between
different WCMS on the web.
Compared with conventional distributed AHS the introduced third-party Adaptive
Service follows a different approach in that it seeks to maintain attributes which apply
across a variety of WCMS, i.e. by using content models representing semantic
concepts.
To illustrate the functionality of the third-party Adaptive Service an implementation
example is provided in the next section.
5 Implementation example
Taking the Drupal WCMS as an example this section defines the means by which the
Adaptive Service can effect the recommendation of content to the user.
44
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
User Content
Model Model
Strategy
Model
Figure 2 exemplifying a basic adaptive integration within the Drupal WCMS.
As indicated in figure 2 the basic Drupal search module was activated. Furthermore
the Drupal hook_search_preprocess is used to intercept the user’s query and send it to
the Adaptive Service. In addition to the query interception, content related user
activities are logged with Drupals node_hook_api. It registers content related
activities and saves these in the underlying database. This information is then used to
extend the user model of the Adaptive Service.
The Adaptive Service on the other hand has to handle the incoming information in
order to send adaptive recommendations back to the WCMS. For this the Adaptive
Service implements a JBoss Rules engine based on APeLS [4]. This engine allows the
usage of flexible adaptive strategies manifested as individual rules. Based on the
example illustrated in figure 2 the following steps are executed by the Adaptive
Service:
x The Adaptive Service identifies and authenticates the user.
x The Adaptive Service waits for information to be sent from the Drupal
based WCMS about the user’s activities.
x After the user issues a query it is intercepted by Drupals
hook_search_preprocess which sends it to the Adaptive Service.
x In addition the Adaptive Service can receive information about the user
content related interactions from Drupals hook_node_api.
x Based on the available user and content model information a specific
adaptive strategy is activated.
x The activated adaptive strategy orchestrates the information provided in the
user and content model and uses it to augment the query.
x The Adaptive Engine sends the augmented query back to the WCMS.
x The WCMS executes the query and presents a personalized ranked list to
the user.
This example illustrates a query interception and query augmentation scenario for
Drupal. In this case the final result is a personalized ranked list. However this
approach allows more complex adaptive scenarios like adaptive navigation support
and adaptive presentation necessary for the overall research illustrated in figure 1.
45
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
6 Architecture
This section describes the overall architecture of the third-party Adaptive Service and
its integration with different WCMS. The Adaptive Service is based on APeLS [4]
and uses pluggable rule engines to facilitate the wide variety of WCMS architectures.
This architecture addresses three main challenges: (a) the sending of user and domain
information as input for the overall personalization process from the WCMS to the
Adaptive Service, (b) the processing of the send information by the Adaptive Service
(c) the creation of appropriate adaptive recommendations by the Adaptive Service to
personalize the output of the WCMS. Please note figure 3 illustrating the overall
architecture.
W
WCMS A
S
AdaptiveService UserModellingService
Unified
WCMS B
W W UserModel W W
User Model
WCMS A
User Model
WCMS B
User Model
WCMS C
S S
S S
Strategy Content User Model
Unified
Model Model
W
WCMS C
S
Figure 3 indicating the overall architecture of the third-party Adaptive Service
The input for adaptive personalization across independent WCMS is based on the
user’s browsing behaviour. This behaviour is collected by the WCMS and delivered
to the Adaptive Service through a Web Service (WS) interface in the back-end of the
WCMS. The user simply navigates within and between the different WCMS with a
standard browser and is not explicitly aware of the back-end integration. This allows
the user to remain in full control of the browsing experience.
The processing of all relevant information including the user and the domain model is
handled by the Adaptive Service. For this the Adaptive Service communicates with an
additional user modelling service e.g. FUMES [15] which provides a unified user
model reflecting the current and previous browsing experience across separate
WCMS. Together with a content model, which stores all information available about
the structure and nature of the content within the WCMS, the Adaptive Service can
compose an appropriate adaptive strategy reflecting the overall intent of the user.
Based on the appropriate adaptive strategy the Adaptive Service can send adaptive
recommendations to the WCMS. The WCMS can use these recommendations to
create a personalized output for the user.
46
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
The most significant feature of the introduced architecture is placing the Adaptive
Service behind the WCMS allowing the user to retain the current browsing paradigm
of free web navigation.
7 Conclusion and Future Work
This paper addresses the open corpus problem by introducing a third-party Adaptive
Service providing adaptivity across different independent WCMS. The novelty of this
approach is the complete separation of the Adaptive Service and the content host i.e.
the WCMS. For this the Adaptive Service discretely connects with the WCMS
providing non-intrusive adaptive recommendations. The user does not have to be
aware of the adaptive interventions, thus this approach retains the current browsing
paradigm of free navigation on the web. Furthermore the non-intrusive nature of the
adaptive interventions maintains the branding, look and feel and operation of the
individual websites modified.
To illustrate the usage of the third-party Adaptive Service a use case was provided
and later specified by an implementation example proving third-party Adaptive
Service integration with a Drupal based WCMS. However the example illustrates
only one possible adaptive application within the overall architecture introduced.
Further developments towards more sophisticated personalization include more
flexible content and link adaptation. However the introduction of such advanced
adaptive functionalities strongly depends on the architecture of the different WCMS.
In order to gauge the feasibility of working with different WCMS a survey was
discussed which indicates general key challenges for the integration of a third-party
Adaptive Service in WCMS.
Future work will concentrate on three connected areas: (1) the integration of
additional WCMS into the adaptive service framework, (2) the extension and
empirical evaluation of resulting adaptive logic/strategies and (3) the further
integration of a unified user modelling approach across different WCMS.
Acknowledgements. This research is supported by the Science Foundation Ireland
(grant 07/CE/I1142) as part of the Centre for Next Generation Localisation
(www.cngl.ie) at Trinity College, Dublin.
8 References
[1] Brusilovsky, P.: KnowledgeTree: A distributed architecture for adaptive e-learning. In:
Proceedings of The Thirteenth International World Wide Web Conference, WWW 2004
(Alternate track papers and posters), ACM Press 104–113. (2004)
[2] Brusilovsky, P. & Henze, N.: “Open Corpus Adaptive Educational Hypermedia”. In The
Adaptive Web: Methods and Strategies of Web Personalisation, Lecture Notes in
Computer Science, vol. 4321, Berlin: Springer Verlag, pp. 671-696. Berlin (2007).
47
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
[3] Brusilovsky, P., Sosnovsky, S. A., & Shcherbinina, O.: User Modeling in a Distributed E-
Learning Architecture. Paper presented at the 10th International Conference on User
Modeling (UM 2005), Edinburgh, Scotland, UK, July 24-29, 2005.
[4] Conlan, O., Hockemeyer, C., Wade, V., Albert, D.: Metadata driven approaches to
facilitate adaptivity in personalized eLearning systems. Journal of the Japanese Society
for Information and Systems in Education 1(1) 38–45 (2002).
[5] Dagger, D., Conlan, O., and Wade, V. P.: An architecture for candidacy in adaptive
eLearning systems to facilitate the reuse of learning Resources. In: Rossett, A. (ed.) Proc.
of World Conference on E-Learning, E-Learn 2003, Phoenix, AZ, USA, AACE 49-56
(2003).
[6] De Bra, P., Smits, D., Stash, N., The Design of AHA!, Proceedings of the ACM
Hypertext Conference, Odense, Denmark, August 23-25, 2006 pp. 133, and
http://aha.win.tue.nl/ahadesign/, (2006).
[7] Drupal Community Page, http://drupal.org/getting-started/before/overview. (Last access
25.02.2009)
[8] Kay, J., Kummerfeld, B., and Lauder, P. Personis: A server for user modeling. In: De
Bra, P., Brusilovsky, P. And Conejo, R. (eds.) Proc. of Second International Conference
on Adaptive Hypermedia and Adaptive Web-Based Systems AH'2002, Málaga, Spain, pp
201-212 (2002).
[9] MediaWiki Foundation, http://www.mediawiki.org/wiki/MediaWiki (Last accessed
16/03/2009)
[10] Semantic MediaWiki, http://semantic-mediawiki.org/wiki/Semantic_MediaWiki (Last
access 16/03/2009).
[11] Semantic Drupal, http://drupal.org/node/299584 (Last access 16/03/2009).
[12] Smarter Wikipedia, http://en.wikipedia.org/wiki/Smarter_Wikipedia (Last access
16/03/2009)
[13] Trella, M., C. Carmona, and R. Conejo: MEDEA: an Open Service-Based Learning
Platform for Developing Intelligent Educational Systems for the Web, in Workshop on
Adaptive Systems for Web-Based Education: tools and reusability (AIED'05). 2005:
Amsterdam, The Netherlands. pp. 27-34 (2005)
[14] Vidgen, S. G: Content, content, everywhere... time to stop and think? The process of web
content management. Computer and Control Engineering Journal. Vol. 13, No. 2, pp. 66-
70 (2002).
[15] Walsh, E., Dagger, D. and Wade, V.P., Supporting “Personalisation for All” through
Federated User Modelling Exchange Services (FUMES).
in Towards User Modelling and Adaptive Systems for All Workshop at User Modelling
07, (Corfu, Greece, 2007).
48
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Investigating a thematic approach to narrative
generation
Charlie Hargood, David E Millard, Mark J Weal
LSL, Department of Electronics and Computer Science, University of Southampton,
Southampton, England
cah07r@ecs.soton.ac.uk,dem@ecs.soton.ac.uk,mjw@ecs.soton.ac.uk
http://www.lsl.ecs.soton.ac.uk/
Abstract. Adaptive hypermedia aims to create a tailored experience for
users and with narrative generation this dynamic content can be in the
form of engaging stories. Narrative generation systems range from the
automatic generation of bespoke stories to the representation of existing
information as narrative. However narrative generation systems often
produce bland and unvaried stories. In this paper we propose that the
inclusion of themes will enrich the resulting narrative and explore how
a prototype thematic system might be integrated with existing methods
of narrative generation. This investigation reveals that integration at the
generation of story elements is important to avoid constraints on desired
themes, that the detailed characters fundamental to character centric
narrative generation make integration difficult, and that integration must
be done carefully to avoid damaging the resulting narrative.
Key words: Adaptive hypermedia, narrative, narrative generation, the-
matics
1 Introduction
The presentation of relevant media in an engaging fashion to users is a difficult
challenge, a user constructing a presentation of information or media from a
personal collection can often have difficulty finding items relevant to each other
and to the task at hand as well as presenting them in a flowing an engaging
manner. Adaptive Hypermedia systems create a dynamic experience for users
by adapting content and navigational choices. Their goal is often to create a high
quality experience that is tailored to the user’s needs and requirements, and to
avoid problems of information overload [5]. Narrative systems are a particular
type of adaptive hypermedia application that attempt to generate content within
a narrative or story framework. However, limitations with narrative generation
methods can compromise the quality of the resulting experience, with stories
that amount to a list of actions of characters who coldly state their motivations
and pursue them directly in steps without any elaboration or subtlety.
Narratives, or stories, are a prevalent representation of human experience
that can engage and entertain. Work in the field of narrative generation presents
49
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
a potentially powerful solution to the problem of generating engaging and rele-
vant information dynamically. Narrative generation seeks to automatically create
bespoke narratives for a variety of uses, either generating requested narratives
from scratch or by representing existing information as a narrative.
Existing narrative generation systems while often successfully generating
short narrative can find their results bland or unvaried depending on the limita-
tions of their approach. We suggest a thematic approach to narrative generation
where the addition of themes will enrich generated narratives making them closer
to human authored narratives with a thematic objectivity beyond the base com-
munication of the information present within the narrative.
A thematic model has been developed [9] based on the work on thematics
in narratology [17]. The model describes themes within a narrative being built
of themes and motifs and how they are connoted and denoted from elements of
the narrative itself. This was further developed into a prototype, the Thematic
Model Builder (TMB) that could score narrative segments on their relevance to
desired narratives, and an evaluation is being performed into the effectiveness of
the system and model at representing and connoting themes.
The focus of this paper is how such a thematic system could be integrated
with existing narrative generation approaches in order to enrich the resulting
narratives. We review existing approaches to narrative discourse generation and
explore at what level a thematic system should be involved with narrative gen-
eration, what approaches it best compliments, and what benefits are likely to
emerge from an integration.
2 Background
2.1 Narratology
Narratology is the study of narrative within literature and as such is primarily
focused on the analysis of narrative. However it does provide a useful insight
into how stories are constructed.
Structuralism is an area of narratology concerned with deconstructing nar-
ratives to identify the components from which a story is built and the structures
that they build within a story. Because of the tangible nature of structuralism its
ideas are very useful for narrative generation as its clear definition of structures
and elements give an insight into what narrative generation systems should be
generating. Most structuralists assert that a narrative is composed of an au-
thored sequence of human experiences [13], and as such may be deconstructed
into two important components; story, and discourse [4]. The story (or fabula)
is a collection of all the information to be communicated and the discourse (or
sjuzhet) represents the exposed parts of the story that are told and how they
are presented (shown in Figure 1).
The story element is the sum of all experiences and elements that make up
the narrative. The discourse represents what parts of the story are exposed in
the narrative (the story selection) and how it is told (the story presentation).
50
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Fig. 1. A narrative can be deconstructed into story and discourse
Discourse is a complicated process concerning many different decisions in-
cluding how the story is presented, what medium is used, the style, the genre,
and the themes of the narrative. Thematics approaches themes with a structural-
ist method of deconstruction and identifies the narrative elements that commu-
nicate themes.
Tomashevsky identified the thematic elements of themes (broad ideas such
as ‘politics’ or ‘drama’) and motifs (more atomic elements directly related to the
narrative such as ‘the helpful beast’ or ‘the thespian’) [17]. He explains a struc-
ture of themes being built out of sub-themes and motifs. A motif is the smallest
atomic thematic element and refers to an element or device within the narrative
which connotes in some way the theme. Themes may always be deconstructed
into other themes or motifs whereas a motif may not be deconstructed.
2.2 Narrative Generation
Narrative generation systems use a variety of different approaches and have a
wide range of objectives. While many systems seek to generate full narratives for
entertainment such as the virtual storyteller [16] and AConf [15] some systems
use narrative generation to add additional meaning to information by represent-
ing it as a narrative using narratological devices like sequencing, emphasis and
omission such as in Topia [3] and adaptive hypermedia systems like AHA! [8].
As a process narrative generation can be broken down into three stages; story,
plot, and presentation generation. Depending on the project in question these
stages can be consolidated together or separated, (for example, in the virtual
storyteller, presentation generation is broken down in narration and presenta-
tion [16]). The majority of narrative generation projects deal with the creation
of the narrative elements (story generation); resolution of the sequence of events
that comprise the narrative and selection of narrative elements to be exposed
and building of relationships between these elements (plot generation); and pre-
sentation of the narrative through a chosen medium (presentation generation).
Figure 2 illustrates this process.
According to Riedl and Young [15] narrative systems take either a character
or author centric approach depending on whether the system seeks to model the
characters within the story, the authorial process itself, or whether the system
51
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
is a compromise of both approaches. [15] also identifies a third approach in the
form of story centric approaches these are however less common and due to their
more linguistic focus are less relevant to this research.
Fig. 2. Narrative generation can be broken down into three stages
Character Centric Character centric narrative generation revolves around
the perspective of modeling the behavior and goals of the characters of a story.
With the characters successfully simulated they are released to pursue their
goals and their actions are exposed, the idea being that stories are everywhere
and an engaging narrative will naturally emerge from the actions of a set of
well-motivated characters.
Character centric narrative generation systems often use agent technology to
suitably simulate the characters and their behaviors with a purpose built agent
taking the part of each character such as in work by Cavazza [7] and in the
Facade system [12] (Facade is not entirely character centric, but its approach is
very similar). Sometimes the intelligence is much more simplistic and a reasoning
system will handle the goals and behavior of all characters, such as in TaleSpin
[14]. However, these systems lack the power to generate varied narratives and
although short simple stories are generated the lack of in-depth modeling of
individual characters behavior removes personalized variety from their actions.
Automatic generation of story elements is rare in character centric narra-
tive generation. This is because elegantly written characters with sophisticated
behavior are key to narratives being successfully emergent from the generated
result and at present the only way to ensure this is to build the characters by
hand. Some story elements are generated by using character archetypes with
cliche behavior such as with the supporting characters in work by Cavazza [7]
but it is rare to find this for key characters.
Plot generation in character centric generation is therefore a direct result of
the characters behavior as dictated by the agents playing them or the intelligence
modeling all of the characters. The actions they take to achieve their goals builds
the relationships between story elements and the sequence of events that makes
a plot. Presentation generation is not specifically tied to the character centric
approach but the focus on entities and modeling their actions make character
centric approaches ideal for presentation in game engines (for example AConf
used the UT engine through the mimesis project [18]). Although the presentation
of character centric systems still sometimes uses text as a medium of choice either
52
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
using sentence templates such as in talespin [14] or generated text using natural
language processing.
The main weakness of character centric narrative generation is its reliance on
an engaging narrative successfully emerging from the exposition of the characters
actions. Often these systems generate bland stories that merely report on a series
of uninteresting actions. These stories are thus often sensible and varied but lack
narrative richness or interesting plot.
Author Centric Author Centric narrative generation seeks to model the au-
thorial process itself rather then the content of the narrative. The systems seek
to model the process by creating rule based systems or narrative grammars that
use well defined structures that are typical of the desired genre of narrative in
order to generate stories.
Author centric narrative generation also lends itself better to the representa-
tion of existing knowledge as narrative as its story elements are not necessarily
the narrative devices such as characters and objects but the devices the author
needs to construct a story. Systems such as ArtEquAKT [2] create narratives
out of a variety of resources and media from the internet and for this project
story generation is the compilation of these resources. The same could be said
for narrative influenced hypertext systems such as Topia [3].
Some systems do model the contents of the narrative to be generated as part
of story generation but remain author centric. Universe [11] builds stories around
a set of author goals and constructs a structure for a story to satisfy these but
does so using the actions of characters modeled from cliche archetypes and a
finite set of actions. In other author centric systems the story structure is not
explicitly generated, but emerges from the selection of a predefined set of story
elements, such as in Card Shark [6].
Plot generation in these systems is a case of applying the rules of the sys-
tem for the desired genre, utilizing the grammar with the available resources,
or filling a story template with appropriate resources. Presentation for author
centric systems is often text based, either using templates such as Universe[11]
or Artequakt [2] or simply exposing the elements in sequence such as in Card
Shark [6].
Author centric systems tend to be highly specialized for one particular type
of narrative, making them inflexible and also often not with a view to generic
narrative generation. The stories are seldom varied as they all follow a similar
authoring process with the same rules and/or grammars and as such can generate
engaging but not often varied narratives.
Compromise Approaches Many narrative generation systems often seek a
compromise between these two approaches in order to counteract the weakness
of using one approach or another. Some systems such as Facade[12] and Uni-
verse[11] will only make slight compromises, such as the ideal story drama curve
approach in Facade or the choice to model characters in Universe, but others
make much larger steps towards marrying the two approached.
53
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
The virtual storyteller [16] at first seems to be a character centric approach
that uses agents to model the behavior of its characters, the difference arises with
the addition of an extra director agent. The director agent has a set of rules
about what makes an engaging story, much like an author centric approach,
and uses these rules to influence the narrative by vetting character actions,
influencing them by giving them new goals, and creating story events to channel
the emergent narrative into being more engaging.
AConf[15] models each ‘actor’ as an expert system seeking to achieve its goals,
giving it characteristics of a character centric approach, but it is fundamentally
more author centric as its process of plot generation centers around the structure
of the narrative building it as a network of events using story planners.
The presentation generation for these systems also vary. In the virtual story-
teller [16] the director agent directly communicates with a narrator and presenter
to generate text using sentence templates whereas AConf [15] uses its character’s
modeling and plot plans to interact with a system called mimesis [18] which uses
the UT game engine to present the narratives.
These systems experienced mixed success with both reporting the generation
of successful narratives. However both suffered from similar problems to charac-
ter centric approaches, while the addition of measures to ensure the narratives
structure is engaging does have a positive effect the engaging narrative can at
times still fail to emerge from the result and the systems can be reliant of sto-
ries that are heavily predefined at the request stage rather then being entirely
generated.
3 A Thematic Approach
3.1 The Thematic Model
Using a thematic model [9] based on Tomashevsky’s work to describe how themes
are constructed within a narrative we propose a thematic underpinning to nar-
rative generation. The basis of the model (as illustrated in Figure 3) is built of
natoms (narrative atoms) which contain features that denote motifs which in
turn connote themes.
For example, we might view a digital photo as a natom, and the tags on
that photo as the features that denote a particular motif. Thus a photo tagged
with ‘daffodil’ could denote the motif of ‘flower’, which connotes the theme of
‘Spring’. Themes can themselves build up into new themes, for example the
theme of ‘Christmas’ can be used to connote the theme of ‘Winter’.
3.2 The TMB
To facilitate an evaluation of the effectiveness of the model a prototype was built
that could use an instance of the model to select images from a group of Flickr
1
images based on their ability to connote a desired theme. The prototype went
under the working name of the Thematic Model Builder (TMB).
1
http://www.flickr.com
54
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Fig. 3. The Thematic Model
As an original instance of the model four themes were modeled (Winter,
Spring, celebration, family) along with all sub themes and motifs of these themes,
XML was used to build this instance. Defining an instance of the model for par-
ticular themes is a complex and subjective process. We explored a systematic
method for building themes based on semiotics [9]. Initially we identify what con-
notes the desired theme, these connotative signs make up the themes sub themes
and motifs. However, these signs become sub-themes only if when expanded all
of their connotative signs in turn connote the original theme, otherwise they
are a seperate (if associated) theme. Connotative signs anchored to a specific
element within the narrative become motifs which have their features defined by
likely tags that denote the element.
The prototype was written in java with a simple JSP front end and Flickr
was used as a source of natoms. As a folksonomy its items have rich semantic
annotations in metadata [1] as opposed to the automatically generated metadata
present in some other media collections. This makes the features in each image
apparent and it also has a large freely available body of resources. The library
of images (the fabula) was generated by making a keyword search of Flickr on
the desired subject and storing the top n images (where n is the desired size).
The system then followed an algorithm of measuring the thematic quality of
each natom in the fabula. It returns the natoms with the highest scores according
to two metrics:
– Component coverage: the proportion of high-level sub-themes or motifs that
a natom has features for - this is useful for measuring how strongly a natom
55
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
matches the desired theme. (for example, winter expands several high-level
sub-theme and motifs including christmas, snow and cold. A natom matching
just one of these has less coverage than one that matches many)
– Thematic coverage: the proportion of desired themes that a natom has fea-
tures for - this is useful for searches with multiple themes
The TMB prototype allows us to compare the effectiveness of selecting photos
according to their theme with the process of selecting photos based directly on
their tags. A pilot evaluation of the prototype has been completed in [10], early
results are promising and show the TMB successfully compiling collections that
have been evaluated as better connoting the desired themes, and performing
better in a narrative context then standard keyword selection.
4 Integration
Referring back to the division of narrative generation illustrated in figure 2, we
can explore the possibility of a thematic systems involvement at different levels
of narrative generation. Themes are intangible concepts, a subtext rather then
a core focus of the narrative, and for this reason it seems at first that narrative
generation would be benefit from thematic involvement at the presentation level.
Here themes could be connoted by emphasis given through the presentation to
the features within the narrative that denote motifs which in turn connote the
desired themes. At this level a thematic subtext would become present through
elaboration on the presentation of the plot. However this is a process that could
potentially fail if there were no relevant features present in the narrative that
could be elaborated upon to help connote the desired theme, the system might
find that at the presentation level a thematic system might only be able to offer
from a subset of themes.
At the story level of narrative generation a thematic systems involvement
would be in some ways the opposite of its involvement at a presentation level.
Instead of offering elaboration on existing narrative features at the story level a
thematic system would generate additional narrative elements based on a shop-
ping list of required motifs for the desired themes. This way themes would be-
come apparent through the presence of certain story elements that connoted the
desired themes. This could potentially fail however if the systems plot genera-
tion did not make use of the thematic story elements or they were not properly
exposed possibly leading to absence of key motifs. Also, such an approach could
damage the generated narrative more then help it potentially flooding the system
with elements irrelevant to the plot. For some systems as well story generation
integration is not always an option, at least on a fully autonomous level, with
many systems generating plot out of pre written and defined story elements.
These semi automatic approaches to story generation require a very different
approach perhaps with thematic guidance on the creation of these elements as
supposed to influencing the automatic generation process in others.
At the plot generation level thematics could play a role in the story selection
of narrative elements as well as the way relationships build. The first part of this
56
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
would be similar to how the TMB prototype builds photo montages in that a list
of desired motifs would be compiled and this would be used to thematicly score
potential story elements and as such influence their selection and inclusion in the
plot. Also, the relationships between story elements and actions of elements could
in turn be factored in as features that denote motifs, as such potential actions
at the plot generation of the story could be thematicly scored influencing what
occurs. For example a story in which violence is a desired theme might see the
protagonist kill the antagonist rather then banish or imprison them. However,
like inclusion at the story level it is possible that heavy thematic involvement
could damage the plot itself, making its involvement a dangerous balancing act,
potentially forcing plot actions that damage the quality of the narrative. Fur-
thermore like involvement at the presentation level, a lack of complete control
over the story elements could potentially restrict available themes.
On the question of which approach to take character centric approaches are
perhaps the most different from the current implementation using the thematic
model. Rather then the natoms of narrative segments that our model describes,
character centric approaches start by simulating the content of the narrative
itself, modeling characters, locations, entities, and events. However, through the
process of plot and presentation, character centric approaches still go on to gener-
ate natoms that contain features and by extension denote motifs. An integration
would have to seek to ensure that certain features were planted in order for the
themes to become apparent in the finished narrative. To do this involvement
at the story level seems obvious as this is where the elements present within
the narrative are generated. However, as a more semi automatic approach with
predefined elements is more common then automatic generation at this level
in character centric approaches it could be difficult to integrate a thematic ap-
proach with the prewritten characters. At the plot and presentation levels an
integration seems more possible, potential character actions and story events
can be thematicly scored to influence actions taken to be conducive with de-
sired themes and then presented in a way that emphasises the relevant thematic
content. Character centric generations frequent use of game engines means that
integration at the presentation level may be easier where knowledge of the enti-
ties present in a particular scene is much more exact then in natural language.
However as already discussed a reliance on integration at these levels potentially
limits the available themes.
Author centric approaches are more similar in process to the current imple-
mentation of the thematic approach in that they’re heavily based on structures
and largely concerned with the authoring process rather then modeling the con-
tent of the narrative. The story generation process for some is about composing
a pool from large collections of potential natoms, often from the Web, based on
their relevance to required parts of the narrative structure. This is very similar
to the way the TMB currently puts together selections for montage, and it is
easy to see that with author centric projects that work this way thematic in-
tegration would be a relatively simple process of scoring potential segments to
generate. At the plot level, integration could be a similar process to the inte-
57
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
gration that would be used with character centric approaches, in that elements
selected for exposure could be chosen on their thematic qualities rather then
only narrative ones. However, for rule based systems of plot generation thematic
rules would need to be written for the system. The feasibility of this would need
to be added on a system by system basis. At a presentation level natural lan-
guage generation poses difficulties for thematic integration as a full lexicon for
desired features would need to be developed and integrated with the system.
Forcing it to uses a small subset of words might make the language clumsy and
its important to remember that the thematic model was created with the theory
of structuring a narrative in mind where as the structure of individual pieces
of language is very different. However, for those systems that use templating or
selected pre authored text presentation, using thematics becomes more feasible
where narrative techniques such as emphasis (spatially or visually) can be used
to highlight relevant segments to help connote a theme.
The possibilities apparent from this investigation are summarised in the ta-
ble in figure 4. Decisions and selections made in generation may be influenced
thematically by making the objective of the decision thematic as well as for plot
objectives. Further thematic integration can be achieved through emphasis at
the presentation or plot levels and other presentation choices such as style may
have an influence that could be worked in favor of desired themes.
5 Future Work and Conclusion
In this paper we describe an investigation into the potential challenges of inte-
grating a thematic system with narrative generation. It is possible that a the-
matic approach may improve the quality of narrative generation by enriching
the resulting narratives which, could give adapted hypertexts tailored to the
user and of a high quality. However, the question of integration between nar-
rative systems and thematics is a complex one. At what point in the process
of generation should there be thematic influence and what style of approach or
compromise makes the prospect of a thematic narrative generation system most
feasible?
Narrative generation is a rich and varied field with a wide variety of ap-
proaches. This variety is maintained in modern work and testament to the fact
that no single perspective is a perfect solution to the problem, with this compro-
mise approaches are becoming more popular as systems aim to find a successful
middle ground. The complexity of the problem also means there are multiple
stages of a system that it being integrated could exert an influence and effect
the resulting narrative in different ways, all of which pose different constraints.
It seems that a combination of issues make integrating thematics with charac-
ter centric narrative generation difficult. As the quality of such systems is reliant
on rich and complex characters, they are often authored by hand which makes
influencing the stories fundamental elements in an automatic way difficult, at the
same time, abandoning thematic involvement at this level instigates constraints
on the available themes to be used at later levels. These constraints mean that
58
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Fig. 4. Summary of potential integrations of a thematic system with narrative gener-
ation
thematic involvement at the story level (the initial generation of elements) is
important to assure a wide variety of available themes. However, in order to
assure they are exposed correctly involvement at either the plot or presentation
level would be necessary as well. Similarities between parts of plot generation for
both approaches and existing implementations of the thematic model make plot
generation the easier option. The constraints surrounding thematic involvement
at the initial story level however do not necessarily rule it out as a possibility
for integration as compromise approaches may allow for thematic elements to be
introduced to a story using a director agent along side complex characters.
With an initial exploration of the issues complete, the future of this work is
experimentation with integrating thematics and narrative generation. There are
still also many remaining questions surrounding this process such as how the
thematic scoring would be balanced in an effective way so as to include themes
without spoiling a narrative and also how the effectiveness of a resulting system
could be evaluated.
59
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
References
1. H. Al-Khalifa and H. Davis. Folksonomies versus automatic keyword extraction:
An empirical study. IADIS International Journal On Computer Science And In-
formation Systems (IJCSIS), 1:132–143, 2006.
2. H. Alani, S. Kim, D. Millard, M. Weal, W. Hall, P. Lewis, and N. Shadbolt. Au-
tomatic ontology-based knowledge extraction and tailored biography generation
from the web. IEEE Intelligent Systems, 18:14–21, 2003.
3. M. Alberink, L. Rutledge, and M. Veenstra. Sequence and emphasis in automated
domain-independent discourse generation. In Information systems, pages 1–10,
2003.
4. R. Barthes and L. Duisit. An introduction to the structural analysis of narrative.
New Literary History, 6:237–272, 1975.
5. H. Berghel. Cyberspace 2000: dealing with information overload. Commun. ACM,
40(2):19–24, 1997.
6. M. Bernstein. Card shark and thespis: exotic tools for hypertext narrative. In
Proceedings of the twelfth ACM conference on Hypertext and Hypermedia, 2001.
7. M. Cavazza, F. Charles, and S. J. Mead. Agents interaction in virtual storytelling.
In Intelligent Virtual Agents, Springer Lecture Notes in Artificial Intelligence 2190,
pages 156–170. Springer-Verlag, 2001.
8. P. DeBra, A. Aerts, B. Berden, B. de Lange, B. Rousseau, T. Santic, D. Smits,
and N. Stash. Aha! the adaptive hypermedia architecture. In Proceedings of the
fourteenth ACM conference on Hypertext and hypermedia, pages 81–84, 2003.
9. C. Hargood, D. Millard, and M. Weal. A thematic approach to emerging narrative
structure. In Web Science at Hypertext08, 2008.
10. C. Hargood, D. Millard, and M. Weal. Using a thematic model to enrich photo
montages. In Proceedings of Hypertext 09, 2009.
11. M. Lebowitz. Planning stories. In Program of the Ninth Annual Conference of the
Cognitive Science Society, volume 9, pages 234–241, Seattle, Washington, 1987.
Cognitive Science Scoiety Conference.
12. M. Mateas and A. Stern. Faade: An experiment in building a fully-realized inter-
active drama. In Game Developers Conference, 2003.
13. M. McQuillan. The Narrative Reader. Routledge, London, 2000.
14. J. R. Meehan. Tale-spin, an interactive program that writes stories. In In Proceed-
ings of the Fifth International Joint Conference on Artificial Intelligence, pages
91–98, 1977.
15. M. O. Riedl and R. M. Young. Character-focused narrative generation for execu-
tion in virtual worlds. In Proceedings of the International Conference on Virtual
Storytelling, pages 47–56, 2003.
16. M. Theune, S. Faas, A. Nijholt, and D. Heylen. The virtual storyteller: Story
creation by intelligent agents. In TIDSE 2003: Technologies for Interactive Digital
Storytelling and Entertainment, 2003.
17. B. Tomashevsky. Russian Formalist Criticism: Four Essays, chapter Thematics,
pages 66–68. University of Nebraska Press, 1965.
18. R. Young. Story and discourse: A bipartite model of narrative generation in virtual
worlds. Virtual Reality, 2003.
60
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Versioning in Adaptive Hypermedia
Evgeny Knutov, Paul De Bra, Mykola Pechenizkiy
Eindhoven University of Technology, Department of Computer Science
PO Box 513, NL 5600 MB Eindhoven, The Netherlands
debra@win.tue.nl, {e.knutov, m.pechenizkiy}@tue.nl
Abstract. This paper presents an approach that uses the terms, operations and
methods of versioning applied to the Adaptive Hypermedia (AH) field. We
show a number of examples of such a use which helps to facilitate authoring,
managing, storing, maintenance, logging and analysis of AHS behaviour,
providing extensive flexibility and maintainability of the systems.
Keywords: Adaptive Hypermedia, Versioning Systems, Revision Control,
Authoring, User Model Updates, Context Changes.
1 Introduction
Versioning (also known as revision control, source control or code management) is
the management of multiple revisions of the same unit of information. It is commonly
used in engineering and software development to manage the development of digital
documentation/code that are usually produced and maintained by a team of software
developers. Changes to these pieces of information are usually identified by
incrementing an associated version and binding it historically with the person, group
or system making the change. On a large scale it is becoming the only way to keep
track of all the changes, perform roll back operations if needed, merge modifications
between different systems, individual users and groups and facilitate provenance
analysis.
It is becoming obvious that tracking all the changes and operations over evolving
structures makes reasonable and feasible to apply versioning methodologies in
adaptive hypermedia systems. In this paper we will consider basic principles and
operations of revision control applications in Adaptive Hypermedia Systems (AHS).
We will not only start investigating the use of versioning for designing the structure
and content of AHS applications but also take a look at the user model evolution in a
versioning context.
2 Background
Engineering version control systems emerged from a formalized processes of
tracking document versions. The main idea was to give a possibility to roll back to an
early state of the document. Moreover, in software engineering, version control was
61
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
introduced to track and provide access and control over changes to source code.
Nowadays it is widely used to keep track of documentation, source files,
configuration settings, etc.
As a system is designed, developed and deployed, it is quite common for multiple
versions of the same system to be deployed with minor or major differences within
different environments, furthermore system configuration/settings, state or/and
context evolve which results in multiple co-existing system versions as well.
If we look at the revision control system as a system used to deliver a certain
version of source code, documents, tables, or any file type or folder to a particular
user at a given time or on request it may resemble delivering adapted content to a user
in an Adaptive Hypermedia System. Of course version control systems are
straightforward and don’t take into account any user model or context changes, don’t
have any semantic or proof layers or any conceptual knowledge representation, but on
the other hand provide very flexible techniques to deliver selected content in a certain
context to a designated user, and facilitate methods to save and track system changes
in a very efficient way.
At the same time AH systems store and process a lot of information, which is
highly sensible to a context data and vice versa - context data itself, is highly dynamic
and influences the adaptation process. Thus tracking AHS alterations and
environment changes is a tightly connected task which requires storage and
computational resources.
3 Revision Control in AHS
Hereafter we consider basic aspects of versioning in application to AHS, provide
analysis of core terms and operations in parallel with AH. We take up major types of
changes in a context of AH systems, models and process flow, thus coming up with a
taxonomy of AH versioning techniques, types of changes and applications areas. As a
result we come up with two examples typical for the AH field: one is an e-learning
application providing an adaptive course and the other is a recommender system. We
encapsulate these examples in a versioning context.
3.1 Types of Changes and Versioning Flow
In a layered structure of a generic AHS [7, 8] we presume that each layer is
responsible for “answering” a single adaptation question [3], like Why?, What?, To
What?, Where?, When and How?. Each layer may have its own data structure and
thus also have its own way of dealing with evolutionary and versioning concepts of
the system. This versioning structure in its turn can be devised and maintained using
different technologies varying from a source control application to a historical Data
Base. We don’t investigate in the paper which technology is best suited for each of
these layers (or questions), however we will speculate on this question, suggesting
solutions. At the same time we take up basic terms and concepts of versioning and
look at them through the eyes of Adaptive Hypermedia. In figure 1 we sketch the core
components of a layered AH architecture and provide annotations with use-cases. We
62
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
will first discuss versioning terms and operations in section 3.2 and then consider
most of these use-cases in detail in section 3.3 through examples.
!
%
!
!
$ %
!
% & '
"
"
#
Fig. 1 Versioning process highlights
In figure 2 we outline a versioning taxonomy distinguishing types of changes,
applications of versioning methodologies and we anticipate the set of potentially
suitable versioning technologies. There are two major types of changes: structural and
value changes. Both may take place in every layer/sub-system of AHS. For instance,
refining the Domain Model structure and changing the underlying content or updating
User Model values versus adding new properties to the model. Throughout the
adaptation process, from authoring to presentation generation we anticipate the
following versioning application areas:
Authoring – changes made by authors, to create, refine, update the structure and
value parts of the adaptive application (usually these are the Domain Model and the
Adaptation Model).
UM operations/updates – these refer to the user behaviour in the adaptive
environment, tracking changes of the user knowledge, goals, preferences,
achievements throughout system usage. Our UM versioning approach corresponds to
ideas discussed in [4] and can serve as a back-end solution for ubiquitous user
modeling.
Context changes – keeping track of context changes of the whole system as well as
the context of a particular model, value or operation.
63
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
System deployment and analysis – changes done to an AHS to deploy the system in
different environments, usually performed by the domain experts, whereas taking up
the specifics of the domain to set up system logging, and analysis facilities.
We are not discussing technological aspects in depth, but can speculate about
versioning (and related) applications to be used, and can foresee a number of well-
known methodologies such as conventional source control systems and historical data
bases for storing and querying for changes. OLAP technologies would suit to perform
analysis. In addition a variety of custom-build systems (such as ontology versioning
available in OntoView [2]) could also be considered.
Fig. 2 AHS versioning taxonomy
3.2 Concepts and Operations of Revision Control
Here we would like to discuss the basic concepts of revision control and how they
refer to the concept of evolution in AH systems. We will try to give a clear idea of
how a particular concept or operation can be applied and will draw parallels with
evolution and changes in AH through examples.
3.2.1 Basic versioning terms
Baseline – an approved version, usually the most stable, from which all the
consequent versions are derived. In the AH field this is usually the core application,
consequently used in different environment settings, within different user groups and
thus being tuned up for those particular settings, which results in evolution and
therefore new versions of the application. If we talk about UM – then the default
version with which the user started can be considered as the baseline. In case of
further analysis baseline is always the point of comparison of the application
functionality and stability.
64
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Branch – an instance is considered to be branched at a point in time, when from
that time and on, two concurrent but independent versions of the same instance co-
exist. As we have mentioned above, any AHS may result in a new set of settings or
being used by a completely different group of people, thus a tune-up of the system
will be required to meet the new settings or requirements. In these terms every AH
system or model emerges in a branch of the initial baseline, representing a new
authored version of the application (model/sub-system). Hence these systems may co-
exist.
Branch can be also used as a prior concept of the User Model update, presentation
generation or any other functionality which preview or try-out is desirable to analyze
system behaviour. Even though the branch itself may not be used in the forthcoming
version or update, a preview of a presentation or a try-out version of the application or
engine will help to identify, observe and analyze the “what-if” case, and with the
successful outcome commit branched changes, label as a new baseline or a head
revision or merge them. This can be applied in terms of UM as well, considering the
case when committing user properties to the latest application state is not desirable,
however would be advantageous to see what can happen with the user in the new
application environment. Though this UM case deviates from the original concept of
the branch in a source control, it still uses the same principle of a concurrent instance,
and in our case it is mapped on a context of UM in AH.
Head – the most recent commit, in other words the most latest version of the
application/model existing on a single or multiple branches, with the latest
functionality aspects prescribed to this branch(es). For UM the head revision is
always the latest state of the model with all the corresponding values being updated to
the latest state in the application.
Commit – applying changes to a central repository (branched or baselined) from
one or multiple working sources. Usually the authoring and set-up processes require a
number of experts, correspondingly a number of working instances which should
emerge in a baseline version which in turn will require to commit all the authors’
changes. In User Modeling we consider committing the changes to the user model
values. At the same time not all the latest user changes should be committed to the
user model in order to provide system stability (for example as it was done in AHA!
system [5]).
Conflict – conflict occurs when the system can’t reconcile changes made to the
same instance of the structure. E.g. when the same concept properties are changed by
two different authors, trying to commit them in the same course may result in a
conflict which will require reconsideration of a concept structure and manual
interference. Though conflict resolution may not guarantee such a property of the AH
system as confluence, we can anticipate that versioned and annotated structures of the
Domain or Adaptation model will be helpful in confluence analysis.
Change (difference, delta) – represents a specific modification under the version
control. Though the granularity of change may vary from system to system, change
always represents the basic structure of versioning concept. Changes evolve from the
baseline, are branched, become new baselines, are committed, then resolved and
merged. Depending on AH system, different instances can be changed (concepts,
relationships, properties, content, context, rules or even a complete model or sub-
system).
65
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
Moreover considering changes – is the best way to compare system functionality
and settings, which is very important for analysis of inherited and evolved (branched
– in terms of version systems) functionality of AHS.
Merge – in conventional source control systems – merge usually refers to a
reconciliation of multiple changes made to different copies of the same file. In AH
merge can be considered as part of an authoring or set-up process, where all the
development and changes from different authors or domain experts come together. In
general we can perform the merge operation over concepts, relationships, properties,
individual user properties and user groups, ontologies, rule sets, etc. As a result merge
provides a clear picture how (from which sources) the concerned concept or a
property has emerged, facilitating application playback and analysis of changes. In
applications where merge regulates UM values this operation can be granted to the
user as well.
Resolve – is a user intervention in conflict resolution of 2 or more conflicting
versions. We refer this to the authoring stage and let the experts decide on the
outcome, or facilitate end-user resolution when dealing with UM.
Tag, Label – refer to an important snapshot of the system or its part in time
implementing a certain functionality which has to be marked/tagged to settle a new
state of the application.. This may be a stable Domain Model structure or a new user
group with common interests (for instance).
At the same time an explicitly labeled structure of the model may be used in the
context of OLAP (On-Line Analytical Processing). We will elaborate on this case
below.
As we conclude, all aforementioned concepts of versioning and source control as
they are applied purely in software engineering and document control can be
represented in terms of Adaptive Hypermedia Systems, facilitating system flexibility
and extensibility
3.2.2 Versioning operations
Having considered the basic concepts of versioning in the context of AHS, we can
come up with the following classes of operations which will reflect typological and
structural types of changes. The following taxonomy of operations was proposed in
[2] in application to ontology evolution, however here we’re trying to extend and
elaborate it in terms of Adaptive Hypermedia. Hereafter we describe the properties of
versioning operation.
Transformation – is usually a set of actual changes taking place over the evolving
structure. These may be: changing properties of concept, classes (in case of
ontologies), adding or removing concept structures.
Conceptual changes (may include concept and concept relationship changes) will
refer to conceptual and abstract changes of the representation, structure and
relationships within the AH system. This type of changes includes changes of types,
relations, conceptual representation of a knowledge. It may also include relations
between constructs of two versions of the model. Conceptual changes should be
always supervised and carried out manually.
Descriptive changes – usually deal with metadata describing the reason,
intentions, author’s credentials, etc., regarding the new version of the model,
66
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
ontology, relation or a concept. Descriptive changes don’t contribute to the actual
change, however may help to reason over different versions of the same instance.
Context changes - will describe the environment in which the current update was
made and in which it is going to be valid. At the same time all the environment
settings for a particular change can be considered as a context change. E.g. changing a
concept in the Domain Model we can consider the state of all the concept
relationships as well as some other Domain specific information as a local context of
this change. At the same the complete system environment is a context of embedding
a new adaptive engine or re-organizing user groups. As we can see from these
examples – context changes can be and usually are the most space and effort
consuming, moreover domain experts usually analyze all the modifications in terms
of contextual changes to capture the complete picture of a particular change.
4 Use-Cases
In order to demonstrate our conceptual view of versioning in AH, we present two
examples that are typical for the AH field.
4.1 E-Learning application use-case
Let’s consider the following: the same discipline is taught in two different
universities, where adaptive courses Course 1 and Course 2 on this subject are
provided to the students (see fig. 3). After one year, a curriculum plan in the first
university (University 1) changes and one of the teachers is asked to change (refine)
the course navigation structure and some of the content which results in a new version
of the course (Course 1 ver.2). At the same time one of the students moves from the
second university (University 2) to the first one (University 1), having received the
credits for a first part of the course (Course 2). The aforementioned teacher is creating
a new version of the course, reusing the complete structure and introducing only
designated changes (in navigation structure, updating adaptive engine with the
associated changes in rules and changing content). Thus the initial version of the
navigational structure is preserved to trace back, compare and analyze how the user
behaviour changes (paths, clickstreams). At the same time the student’s User Model
(which has been created in another university) (UM ver.1) emerges into a new version
(UM ver.2), providing the student and his supervisor the possibility to compare basic
concepts of Course 2, perform reconciliation and merge the corresponding UM values
(of the results that the student has achieved taking the similar course in another
university), and at the same time keep the history of his studies. On the other hand the
automatic concordance is also possible if only the changes made in the course are
corroborated with the additional descriptive information (is accompanied by the
descriptive change (see section 3.2.2)) which contains extra explanations how to
reason and update values (in this case UM values) due to the evolved course structure
and/or content.
The complete picture of courses updates and user (student) development becomes
transparent and the course instructor may trace back all the changes done to the
67
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
course, re-use, update, merge any particular part without creating anything from the
scratch. He can analyze differences in and between courses.
Fig. 3 Versioning adaptive courses
4.2 Recommender system use-case
In our second use-case we would like to outline the advantages of applying
revision control in recommender systems. Typically, comparing a UM state to some
reference characteristics, and predicting the user’s choice, the system evolves from
the initial user profile. Each recommendation step (viewing an item, ranking it and
getting recommendations) corresponds to a change in the User Model, which in a
conventional system is committed to the latest state not taking into account user
interactions and updates. Considering a versioning structure, we can store the
difference in UM between two commits, thus logging user behaviour, and annotating
it with the action (ranking) done by the user at each step. Later such a pattern of
successful behaviour can serve as a recommendation to the other users providing the
provenance of each recommendation step (how was this recommended and when, in
what context, what was the user model state at that point in time and what has
influenced the recommendation). The same happens with the recommended items,
which evolve, can be modified and in general can have their own history of ratings.
If the user moves from one system to another, he will face a problem of the user
profile alignment (like in the previous use-case sec. 4.1), where the history of ratings
that he made may help to resolve conflicts. On the other hand labeling and tagging of
user and system behaviour may become a basis for OLAP analysis. Building an
OLAP cube where numeric facts (or measures), categorized by dimensions can have a
set of labels or associated metadata (which is essentially corresponding to the labels
used in the versioning system) will allow to organize everything in a form of
multidimensional conceptual view and apply ‘slice and dice’ operation as the most
68
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
essential analysis tool in this respect, instead of simple system or user logging and
then applying complicated and time-consuming extraction algorithms. This will
facilitate quick extraction of rating information of a particular date or timeframe, or
for example the set of users who rated a certain product a year ago. The same
approach can be undertaken to version rated items in order to trace back the changes
and associated ratings (as well as corresponding UM values) if the product or its
description or properties change. In figure 4 we briefly summarize versioning aspects
of the recommendation use-case.
Fig. 4 Versioning in Recommender system
To conclude this use-case we would like to outline the ideas and principles used in
a context of Recommender System. A new modification of product in the stock can be
designated by a new version, it inherits corresponding properties and ratings.
Versioning makes possible for products (product concurrent versions) to co-exist. It
also helps to store product updates and a context of these changes efficiently. Thus we
can create concurrent instances of products and ratings within different applications,
inherit ratings, properties and merge these changes. The User Model versioning
allows to analyze user step-by-step behavior (incl. user trend, etc.), compare changes
with other users in order to provide similar recommendation patterns in a case of
successful outcome.
69
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
4.3 Use-cases conclusions:
For the aforementioned use-cases we would like to conclude with a summary of
approaches we suggested in the introduction and outline the advantages of versioning:
Authoring – versioning helps to create, maintain and re-use concurrent versions of an
application, model or a particular property and value (e.g. course and a corresponding
content), saving authoring effort.
Storing – versioning offers an efficient way to store changes, annotate them, label,
present in a hierarchical structure. This saves space for a large scale system and keep
track of the system history.
Maintenance – structured changes and a set of basic concepts and operations (merge,
resolve, commit, tag/label, head and branch) are sufficient to maintain and reconcile
application conflicts, create concurrent versions or comprise functionality
implemented in different systems in one application (merging changes from different
branches).
Logging – logging incremental changes (of the application, user model or a context)
provides playback possibilities and serves as a ground of system analysis. Logging in
terms of UM updates (or steps taken) will provide a basis for comparison of
behaviour patterns and advance provided recommendations.
Analysis – versioning facilitates analysis of the step-by-step system and user
behaviour to identify trends; tagging and labeling can facilitate more complex
analytical approaches (such as OLAP) providing the required structure and
description of the data; hierarchical incremental logging results in a clear and
transparent structure of system changes and an overall evolution picture.
5 Conclusions and Further Work
In this article we tried to map a conventional versioning approach onto the field of
Adaptive Hypermedia, providing clear parallels in terms of versioning concepts and
operations. We tried to make first steps in this direction in order to show advantages
of this approach and outline the perspective of applying these techniques and
methodologies in order to facilitate the transparency of AHS evolution through
versioning.
Considering further work directions we can think of describing layers of a generic
adaptation framework in a versioning context (or essentially looking at the basics of
adaptation through versioning), investigate technologies (e.g. source control,
historical data bases, etc.) that meet the requirements of the framework and come up
with the detailed structure and operations to devise these versioning facilities.
Acknowledgements. This research is supported by NWO through the “GAF: Generic
Adaptation Framework” project.
70
International Workshop on Dynamic and Adaptive Hypertext: Generic Frameworks, Approaches and Techniques (DAH'09)
References
1. Altmanninger, K., Gerti Kappel G., Kusel, A., Retschitzegger, W., Schwinger W., Seidl, M.,
Wimmer, M., AMOR – Towards Adaptable Models Versioning. In 1st International
Workshop on Model Co-Evolution and Consistency Management in conjunction with
Models’08, 2008.
2. Klein M., Fensel D., Kiryakov A., Ognyanov D., Ontology versioning and change detection
on the Web. In Proceedings of In 13th International Conference on Knowledge Engineering
and Knowledge Management: Ontologies and the Semantic Web. Berlin, Heidelberg:
Springer, pp. 247-259, 2002.
3. Brusilovsky, P., Methods and techniques of adaptive hypermedia, User Modeling and User
Adapted Interaction 6(2-3), pp. 87-129, 1996.
4. Heckmann, D., Ubiquitous User Modeling, PhD Thesis. Universitat des Saarlandes, 2006.
5. De Bra, P., Calvi, L., AHA! An open Adaptive Hypermedia Architecture. Hypermedia, 4(1),
pp. 115-139, 1998.
6. Herlocker, J., Konstan, J., Terveen, L., Riedl., J., Evaluating collaborative filtering
recommender systems. ACM Transaction on Information Systems, vol.22, No.1, pp.5-23,
2004.
7. De Bra, P., Houben, G.J., Wu, H., AHAM: A Dexter-based Reference Model for Adaptive
Hypermedia, Proceedings of the ACM Conference on Hypertext and Hypermedia, pp. 147-
156. 1999.
8. Cristea, A., De Mooij, A., LAOS: Layered WWW AHS Authoring Model and their
corresponding Algebraic Operators, The Twelfth International World Wide Web
Conference, Alternate Track on Education, 2003.
71