Mobile devices provide a variety of ways to access information resources available on the Web and a high level of adaptability to different aspects (e.g., device capabilities, network QoS, user preferences, location, an so on) is strongly required in this scenario. In this paper we propose a technique for the efficient adaptation of Web Information Systems. The approach relies on special rules that allows us to specify, in a declarative way, how to generate, in an automatic way, the adaptation specifications that satisfy the requirements of a given context. Rules are classified in a set of clusters and a matching relation between clusters and context requirements is defined. The technique of rule evaluation and clustering guarantee that different contexts and orthogonal requirements of adaptation, possibly not fixed in advance, can be efficiently organized and taken into account in the adaptation process.
Modern Web Information Systems (WIS) are challenged to generate (automatically) a hypermedia presentation built from information that is gathered from different, possibly heterogeneous, sources that are distributed over the Web. Nowadays, given the spread of mobile devices, a novel and fundamental requirement of these systems is the ability to adapt and personalize content delivery according to the context of the client. An important point that needs to be taken into account is that this scenario is very dynamic: some aspects of the context can dynamically change. For instance new users with new preferences can be enabled to access the information system, possibly unpredicted types of access devices can be used, alternative network connections can be made available, further aspects of the context (like the location or others environmental factors) need to be incorporated. Also, the technology used to implement the adaptation can be changed and this should have a limited impact on the overall application. It follows that the adaptation process should guarantee a high level of flexibility in terms of responsiveness to rapidly changing requirements of adaptation and suitable actions to be undertaken to meet these requirements.
In the literature, some adaptation approaches rely on the definition of rules to generate suitable adaptation specifications [2,3,10]. In [5] we have presented a general methodology for context adaptation, based on special rules that model the adaptation at an abstract level, inspired by the approaches cited above. The rules specify, in a declarative way, how to generate, in an automatic way, the adaptation specifications that satisfy the requirements of a given context. A relevant problem is to rapidly select and activate the rules that best fit the requirements of adaptation of the context (in particular when the context changes frequently). In this paper we present an efficient implementation to optimize the activation process of adaptation rules. To this aim, we introduce a clustering technique to classify the adaptation specifications.
The rest of the paper is organized as follows. Section 2 introduces the rulebased approach. In Section 3, we illustrate how to define the set of clusters and the process to efficiently activate a rule, using the clusters. In Section 4 we present a practical implementation and experimental results and finally, in Section 5 we draw some conclusions and sketch future works.
In this section we present special rules to specify, in a declarative way, how to generate, in an automatic way, adaptation specifications. The rules are based on two basic notions: the generic profile and the abstract configuration.
A (generic) profile is a description of an autonomous aspect of the context in which the Web site is accessed (and that should influence the presentation of its contents). Examples of profiles are the user, the device, the location, and so on. A dimension is property that characterizes a profile. Each dimension can be conveniently described by means of a set of attributes. Attributes can be simple or composite. A simple attribute has a value associated with it, whereas a complex attribute has a set of (simple or complex) attributes associated with it.
In this model, a context is a collection of profiles. Figure 1 As an example, given the profiles reported in Figure 1 we have that P 2 P 1 and P 3 P 2 .
We introduce the notion of (abstract) configuration as a triple C = (q, h, s) where:
-q is a query over the underlying database expressed in relational calculus, a declarative and abstract language for relational databases ( [1]); -h is an abstract hypertext definition expressed in WebML ( [4]), a conceptual model for Web application which allows us to describe the organization of Web pages in a tight and concise way, by abstracting their logical features; -s is presentation specification expressed in terms of an original notion of logical style sheet, which is a set of tuples over a predefined collection of Web Object Types (WOTs) like text, image, video, form and so on; each WOT τ is associated with a set of presentation attributes: they identify possible styles (e.g. font, color, spacing, position) that can be specified for τ .
An example of configuration is reported below. It is important to note that a configuration is indeed a logical notion that can be represented and implemented in several ways and with different syntaxes. This property guarantees the generality of the approach with respect to actual languages and tools used to implement the adaptive application. For instance, we can implement a configuration using SQL at the content level, XHTML at the navigation level and a set of CSS files at the presentation level.
The matching relationship between configurations and profiles is represented by means of a novel notion of adaptation rule. An adaptation rule has the form P r : C d ⇒ C f where: The intuitive semantics of an adaptation rule is the following: if the client has a profile P r and the condition C d is verified then generate the configuration C f . An example of adaptation rule for a device profile with the hardware dimension H is the following:
where X, Y , and Z are the parameters of H and {q, h, s} is the following parametric configuration:
Hence, a profile P can activate a rule for a profile that is more general than P . Now, let R be a rule P r : C d → C f activated by a profile P and let C be the configuration obtained from C f by substituting the parameters of P r with the actual values occurring in P : we say that C is generated by P using R.
We assume to have at disposal an initial set of rules S R . In an adaptability scenario, context changes generate events that produce one or more profiles (instances). Each profile (instance) can activate a rule of S R . We should optimize the research to select and activate efficiently the most appropriate rules and generate the most suitable configuration. So we organize S R classifying the rules in a set of clusters. Each cluster represents a class of adaptation that matches the requirements of a class of context.
We define a distance that allows to compare profiles. We take advantage of the tree structure of the generic profile. We get inspiration from the Tree Edit Distance [9], where the distance between two trees T 1 and T 2 , that we indicate as d ted (T 1 , T 2 ), depend on the sequence of operations (chosen in a limited predefined set) that transforms T 1 into T 2 . We assign a fixed cost to each operation: the distance between the considered trees is the sum of essential costs for the transformation. For our case, let's consider the set of operations edit, remove and add, respectively to modify the content of a node, to delete a node and to create a new node. In our tree structures, we distinguish two principal types of node: dimension and attribute. We have operations to modify, remove or create dimensions and attributes and we indicate the cost of an operation with γ.
Definition 2 (S-derivation) Given two trees T 1 and T 2 , S = s 1 , ... , s k the sequence of operations to transform T 1 in T 2 , an S-derivation between T 1 and T 2 is a sequence U 0 , ... , U k of trees resulting by applying the single operation, where U 0 = T 1 and U k = T 2 , and the cost γ(S − derivation) is i=k i=0 γ(s i ).
So we can intuitively define the distance between two profiles P 1 and P 2 , the minimum cost for a S-derivation between them. Definition 3 (Distance between profiles) Given two profiles P 1 and P 2 , we define the distance between them as d ted (P 1 , P 2 ) = min{γ(S − derivation) | Sderivation from P 1 to P 2 }
Let's represent a cluster as a tree where the nodes are profiles. The root represents the minimum set of information that nodes of the tree share. Basically a client is identified by the profile sent to the system. Let's remember that a profile is principally described by dimensions, that characterize the main information, articulated in attributes. So, the root of a cluster is a profile characterized only by dimensions. It will contain the minimum information that several profiles has to include to be in the same cluster. Given a profile P, pruned by all attributes, we can build several beginner clusters, rooted with profiles generated from P, on the number and type of dimensions. However the designer can decide the detail level for the roots. For instance a designer can decide to articulate some dimensions of a root with attributes, to extend the level of detail of the minimum information to share.
We define a cluster as follows Definition 4 (Cluster Tree) A cluster CL is a couple {N CL , E CL } where N CL is the set of nodes (profiles) and E CL is the set of edges (n i , n j ) such that n i n j
We can relate a node P r of a cluster with the rule P r : C d → C f in an Hash table using P r as access key.
Given the set of roots R t = {R t 1 , ... ,R t n } and the set of rules S R , we initialize a set of clusters CL = {CL 1 , ... ,CL n } as follows:
P r , and we navigate the cluster in depth until level k where doesn't exist any node subsumed by P r , (ii) we search at level k −1 the node N d such that N d P r and if there are more nodes N d such that N d P r we choose the node with lowest distance, (iii) we add P r to N CLi and (N d, P r ) to E CLi , (iv) if there are one or more nodes N d i such that P r N d i then we delete any edge of type (N d j ,N d i ) in E CL i and add to it the edge (P r , N d i ),
• for each node of a cluster we add the relative rule to the Hash table.
Built the set of clusters, now we can perform an optimization strategy to activate a rule in an efficient way. Given the set of rules S R , the set of clusters CL = {CL 1 , CL 2 , ..., CL n }, the Hash table H t and a profile instance P I of a profile schema P S , we produce a set of configurations as follows:
1. we initialize P with P S ; 2. we search the cluster CL i in CL, with a root R ti such that R ti P and that has the lowest distance from it; 3. (i) we navigate in depth the cluster until level k where any node, that is subsumed by P , doesn't exist; (ii) we search at level k − 1 the node N d such that N d P and if more nodes are subsumed by P we choose the one with lowest distance; (iii) we extract the rule R l , related in the H t to N d, and if the condition is satisfied, we activate R l and instance the configuration with the value of P I ; (iv) we update P as P -N d; 4. we iterate from step (2.) until P is not empty and a rule that can be activated by P exists; 5. if no rule can be activated in this way, the system will return a default configuration.
Let's assume a client sending a profile P I (see Figure . 2(a)), instance of a profile schema P to the system. Assume also that the system has already initialized its own set of clusters, composed by clusters C 1 and C 2 (see Figure 3). We easily see that the root of the cluster C 2 is the one which subsumes P and has the lowest distance from it. So we navigate that cluster and note that the only child N of the root it is equal to P ; then we extract the rule R l related in the H t to N and if the condition is satisfied, we activate it and instance the configuration with the values of P I . Subsequently, assume that a new profile P I (see Figure 2(b)), instance of a profile P , is sent by another client to the system. At the same way explained before, we see that the root of the cluster that subsumes P and has the lowest distance from it, is cluster C 1 root. Navigating that cluster, we need to confront P with root's two children. We easily see that no one of them is equal to or has a subsumption relation with P : being their parent a root, is not possible to activate its rule; so, as we explained before, the system will return a default configuration. ( n i−1 ) (n − i + 1). These profiles will be ignored by the system, which has only accessed the roots of their clusters, that are not profiles. So, counting also these accesses, we find that at least we obtain to save a number of accesses equal to
n i . This number doesn't take count of the fact that the system won't access all the nodes of the selected cluster, but only some of them, depending on its structure. Anyway it gives evidence that, using this clustering algorithm, it is possible to obtain a certain benefit in terms of number of accesses.
We have designed and developed a practical implementation to test the our approach. The system relies on an RDF database of contents and the selection of data is done by performing RDF queries expressed in SPARQL [8]. We use an RDF(S) representation for schema level and RDF for instance level. The implementation makes use of Jena [6], a Java framework for building RDF based applications. Each rule is implemented in terms of Inference Rule of Jena [7]. Using the Inference Engine of Jena, the system generates a configuration that infers the adaptation on RDF(S) documents. Finally the system returns several response as output, using XSLT transformations on RDF instances. We have tested our system to experiment the effectiveness and the efficiency of the approach illustrated in this paper in several practical cases. On the server side, we used an IBM computer xSeries 225, equipped with a Xeon2 2.8Ghz processor, a 4 GB RAM, and a 120 GB HDD SCSI. The Web site have been accessed by three different types of devices: a mid-range desktop, several PDAs with different capabilities, and some cellular phones. Figure 4 reports the average response time (vertical axis) for each device type (horizontal axis). The Figure shows promising times to produce the adapted response. The Desktop client presents an average time of 72 ms, the PDA client 97 ms and the Wap client 121 ms. The diagram compares the medium response time in absence and in presence of clusters. In particular the system, using clusters, capitalizes the approach for mobile devices, almost halving the response time. For instance the Wap client benefits from 121 ms to 59 ms.
In this paper we have presented a novel rule-based approach supporting the automatic adaptation of content delivery in Web Information Systems. This problem arises in common scenarios where the information system is accessed, in different contexts, by a variety of mobile devices. The adaptation is achieved automatically by means of special rules that specify, in a declarative way, how a configuration can be generated to meet the requirements of adaptation of a given profile. Finally the organization of rules in a set of clusters guarantees the responsiveness of the system in a dynamic scenario. Different contexts and orthogonal requirements of adaptation, possibly not fixed in advance, can be taken into account in this process. The results presented in this paper are subject of further conceptual and practical investigation. From a conceptual point of view, we are currently investigating the expressive power of rules and the generality of clusters. In particular we are improving the distance between profiles, using a comparison between common pathes. From a practical point of view we are improving the efficiency of the system and we are extending its functionality.
We can easily see that using this clustering algorithm we can reduce the number of accesses to S R . In our system, we have seen that a profile given by a client can activate a rule in the default set. So when a client sends a profile to the system it has to search for the most suitable rule in S R . We can assume that the worst case is when the system has the greatest possible number of default rules, that is when the system has in S R one rule for each possible profile that a client can send. Without using clusters we should execute a number of ordered accesses equal to the total number of possible profiles. It is easy to see that the number of possible profiles is the number of profiles obtained with every possible different combination of dimensions and attributes. Assuming to have a complete schema with n dimensions and m attributes for each dimension, we can see that the number of different combinations of dimensions is
). If we use the clustering algorithm, in this case we will obtain a number of clusters equal to the number of different combinations of dimensions, seen above. To access the right clusters, the system has to access to all of their roots and then find the right way on the selected tree. So it can ignore a number of trees equal to n i=1 n i + 1. We can see that in this situation the worst case is when the root of the selected