Context-Aware Presentation of Linked Data on Mobile

Luca Costabello, Fabien Gandon

► To cite this version:

Luca Costabello, Fabien Gandon. Context-Aware Presentation of Linked Data on Mobile. International Journal on Semantic Web and Information Systems, 2014, 10 (4), pp.32. 10.4018/ijswis.2014100103 . hal-01188210

HAL Id: hal-01188210

https://inria.hal.science/hal-01188210v1

Submitted on 27 Sep 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Context-Aware Presentation of Linked Data on Mobile

Luca Costabello
Inria, France

Fabien Gandon
Inria, France

In this paper we focus on context-aware adaptation for linked data on mobile. We split up the problem in two sub-questions: how to declaratively describe context at RDF presentation level, and how to overcome context imprecisions and incompleteness when selecting the proper context description at runtime. We answer our two-fold research question with PRISSMA, a context-aware presentation layer for Linked Data. PRISSMA extends the Fresnel vocabulary with the notion of mobile context. Besides, it includes an algorithm that determines whether the sensed context is compatible with some context declarations. The algorithm finds optimal error-tolerant subgraph isomorphisms between RDF graphs using the notion of graph edit distance and is sublinear in the number of context declarations in the system.

## Introduction

Semantic Web mobile applications might not have built-in assumptions about the schemas of the data they consume, as data models could be unknown a-priori, and provided by heterogeneous sources: users might consume any type of data, as long as it is relevant to their context (Schraefel & Rutledge, 2010). To improve the effectiveness of Linked Data consumption, content adaptation must be adopted, i.e. the process of selecting, generating, or modifying content units in response to a requested URI<fnref n="1" />. Essential in the mobile Web, such process is driven by the multifaceted notion of *client context* (Dey, 2001). Content adaptation reduces the fan-out of RDF entities, and provides coherent information by using context as a dynamic filter. Furthermore, it orders, groups, and formats triples, thus creating “optimized” content units ready for user consumption.

This paper addresses the question of *how to enable context-aware adaptation for Linked Data consumption*. We split up the problem in two sub-questions: i) *how to model context for Linked Data presentation* and ii) *how to deal with context imprecision to select proper presentation metadata at runtime*. Modelling context-aware presentation concepts for Linked Data needs a proper ontology that fills the gap between traditional context ontologies and the Web of Data (e.g. support for future extensions, adoption of a lightweight vocabulary instead of a vast, monolithic context ontology, etc). The selection of presentation metadata is complicated by a series of constraints: first, the intrinsic imprecision of context data determines the need for an error-tolerant strategy that takes into account possible discrepancies between context descriptions and actual context. Second, this error-tolerant mechanism must support heterogeneous context dimensions (e.g. location, time, strings). Third, since the procedure must run on the client-side - to avoid disclosing sensitive context data - we must design a mobile-friendly algorithm, with ac-

ceptable time and space complexity. Finally, the adopted strategy must support runtime updates of RDF graphs, as context descriptions might be fetched from remote repositories and added to the selection process at runtime, and the sensed context may change at any time.

Our contribution is PRISSMA, a context-aware presentation framework for Linked Data. PRISSMA answers our two-fold research question with the following contributions: i) a vocabulary for describing context conditions, compatible with Fresnel (Pietriga, Bizer, Karger, & Lee, 2006), and ii) an error-tolerant subgraph matching algorithm that determines whether the sensed context is compatible with context declarations.

The paper is organized as follows: first we survey state-of-the-art presentation-level frameworks for the Semantic Web. We also provide an overview of error-tolerant matching techniques for RDF. We hence proceed with describing the design principles of PRISSMA, and we introduce the PRISSMA vocabulary. We explain the error-tolerant selection algorithm and provide experimental evaluation results. We present PRISSMA Browser, a proof-of-concept mobile application adopting PRISSMA, and we conclude by discussing the limitations of our approach and future work.

## Related Work

The Haystack platform UI (Ozone), as well as Noadster and Xenon (Huynh et al., 2002; Rutledge et al., 2005; Quan & Karger, 2005) are early works targeting RDF presentation, but they do not support multiple media. Gandon's Surrogates focus on UI representations of SPARQL queries over RDF repositories (Gandon, 2005). Although it supports multimodality, binaries are not available online. Champin's Tal4RDF, and Auer et al.'s LESS are template languages for textual output of RDF (Champin, 2009; Auer et al., 2010).

<footnote n="1">¹See *Adaptation* definition: http://www.w3.org/TR/di-gloss/#sec-glossary</footnote>
<figure><img src="image_2.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b)</figcaption></figure>

<caption>**Figure 1.** A comparison of presentation layers for the Semantic Web (a), and of error-tolerant matching techniques for RDF (b). Full support is identified by ●, partial support by ○, no support by the empty cell.</caption>

They do not adopt standard Semantic Web languages. Dadzie et al present a template-based visualization framework for Linked Data (Dadzie et al., 2011). The proposal takes into account user context, but only in a hardwired, implicit manner. Fernéandez et al. propose a formal Linked Data Visualization Model, LDVM (Fernéandez et al., 2012). They focus on

visualizing data from large-scale RDF datasets, without being domain-dependent. Binaries are not available online. More importantly, as shown in Figure 1a, none of the existing presentation frameworks for Linked Data fully supports context awareness. Fresnel (Pietriga et al., 2006) is a rendering engine for RDF built on the assumption that data and its related schema do not carry sufficient information for representing triples, hence it provides additional presentation-level knowledge. Fresnel relies on Semantic Web standard languages: Fresnel declarations are RDF triples, and developers create Fresnel declarations for RDF instances or classes using the Fresnel RDFS/OWL vocabulary. Fresnel is the only proposal that features a clear separation between *data selection* and *formatting* (Xenon features this distinction as well, but it adheres to a procedural approach): this guarantees independence from the adopted data access strategy (HTTP dereferencing or SPARQL). Data selection and filtering is implemented by *Lenses*, while *Formats* define how to present data. Lenses and Formats can be associated to a *Purpose*, i.e. an extension designed to support basic media-based presentation. Besides, Fresnel is one of the only presentation layer for Linked Data with a binary implementation available online.

A number of ontology-based context models relying on Dey's definition have been proposed in the latter years. It is out of the scope of this paper to survey such works (see Bolchini et al. (Bolchini, Curino, Quintarelli, Schreiber, & Tanca, 2007) and Krummenacher and Strang (Krummenacher & Strang, 2007) for comprehensive surveys).

Castano et al. (Castano, Ferrara, Montanelli, & Varese, 2011) provide an overview of matching techniques for RDF instances; most of these works stem from ontology matching strategies (Euzenat & Shvaiko, 2007). Figure 1b compares error-tolerant works closer to our requirements: iSPARQL (Kiefer et al., 2007) is designed for error-tolerant matching, but it neither supports heterogeneous dimensions (such as location), nor is it designed for computationally-constrained mobile platforms. The Silk framework (Volz et al., 2009) includes geographical and time distances but such metrics do not consider data imprecision. Furthermore, Silk is not designed to run on mobile devices. Gu et al. (Gu et al., 2004; Gu, Pung, & Zhang, 2005) propose a Bayesian approach for dealing with uncertain contexts. They rely on an ontology-based model to describe contexts, and apply Bayesian reasoning. Although being RDF-specific, their approach is designed to run as a middleware, and not on the client side. RDF semantics states that two RDF graphs are semantically equivalent if they entail one another<fnref n="2" />, and, as underlined by Carrol (Carroll, 2002), the important concept for entailment between RDF graphs is *subgraph isomorphism*, known to be NP-complete. Subgraph isomorphism is at the heart of a recent pattern matching engine for SPARQL by Zou et al. (Zou et al., 2012). Unfortunately, the authors do

<footnote n="2">²http://www.w3.org/TR/rdf-concepts/</footnote>
not provide an *error-tolerant* version of their algorithm. It has been proved (Conte, Foggia, Sansone, & Vento, 2004) that finding the optimal error-tolerant subgraph isomorphism between two graphs can be reduced to the computation of *graph edit distance*: the idea is that differences between graphs can be modelled in terms of operations to apply to graphs, such as adding a node or modifying an arc. Graph edit distance provides the required flexibility for building an error-tolerant subgraph matching algorithm, and supports customized and heterogeneous cost functions (comparing contexts means dealing with data such as location, time, string literals, URIs). Nevertheless, computational complexity is exponential in the number of graph nodes, since graph edit distance algorithms assume that every node can be mapped on every node of another graph. Although context descriptions are rather small graphs, computing graph edit distance remains a computationally expensive task, in particular on mobile devices. Traditional approaches to compute graph edit distance between an input graph and a set of reference graphs apply a pairwise comparison, but such methods do not scale well and badly perform with runtime updates (Gao, Xiao, Tao, & Li, 2010). Messmer and Bunke (Messmer & Bunke, 1998) adopt a different strategy: they fragment directed, labelled graphs into smaller subgraphs, and store them into a single data structure, to avoid duplicates. Given an input graph, an online search algorithm searches for the error-tolerant subgraph isomorphisms with the lowest edit costs.

## The PRISSMA vocabulary

We extend the Fresnel presentation-level ontology with context awareness. The choice of adopting the Fresnel vocabulary is mainly justified by Fresnel being domain independent, by the support of multiple data access strategies, and by built-in multimodality that can be effortlessly extended for context awareness. The PRISSMA vocabulary<fnref n="3" /> (Figure 2) broadens the semantics of *fresnel:Purpose* to delegate the selection of Lenses and Formats to a wider and more expressive definition of mobile context, modeled by the *prissma:Context* class<fnref n="4" />. PRISSMA is not meant to provide yet another mobile context model, as that is out of the scope of our work. Instead, we reuse and combine well-known vocabularies. Although specifically designed to model client-generated context data, the vocabulary does not provide a comprehensive, exhaustive model: the approach is to delegate refinements and extensions to third-party domain specialists.

To wrap up each context-aware presentation-level unit of information, the concept of *Prism* is introduced (a Prism is *rdfs:subClassOf* of a *fresnel:Group*):

**Definition 1** (*Prism*). *A Prism P is an RDF graph that describes the context conditions under which a given RDF presentation must be activated.*

The PRISSMA vocabulary is based on the widely-accepted

<figure><img src="image_4.png" /><figcaption>**Figure 2.** The PRISSMA vocabulary at a glance. Grey boxes represent core classes, i.e. the *context dimensions*. Dotted classes picture reused terms from third-party ontologies.</figcaption></figure>

formalization of context proposed by Dey (Dey, 2001). More precisely, it extends the W3C Model-Based User Interface Incubator Group proposal<fnref n="5" /> that describes mobile context as an encompassing term, an information space defined as the sum of three different dimensions: *User* model and preferences, *Device* features, and the *Environment* in which the action is performed. The core of the PRISSMA vocabulary consists in classes and properties that models the aforementioned context dimensions:

**Context.** The Context class represents the mobile context, according to Dey’s context definition (Dey, 2001).

**User.** Represents the target client user associated to a *Context* and consists in a *foaf:Person* subclass. To provide more flexibility, the class can be used to model both user stereotypes and individuals. The property *user* associates a User to a Context.

**Device.** Represents the mobile device on which Web of Data resource consumption takes place, enabling device-specific data representation. *Device* is a subclass of the W3C Delivery Context Ontology<fnref n="6" /> *dcn:Device* that provides an extensible and fine-grained model for mobile device features. The property *device* associates a *Device* to a *Context*.

<footnote n="3">³http://bit.ly/prissma-vocab</footnote>

<footnote n="4">⁴Note that the PRISSMA vocabulary is loosely coupled with the Fresnel ontology via the reuse of the *fresnel:purpose* property (Figure 2). To guarantee full compatibility with existing Fresnel rendering engines, we adopted the Fresnel vocabulary as is, hence we did not update it to OWL2.</footnote>

<footnote n="5">⁵http://bit.ly/XGR-mbui</footnote>

<footnote n="6">⁶http://www.w3.org/TR/2009/WD-dcontology-20090616/</footnote>
**Environment.** Models the physical context in which the Web of Data resource consumption takes place, enabling customized resource representation according to specific situations. Different dimensions are involved in modelling the surrounding environment. The property environment associates an Environment to a Context.

Aside from the core classes mentioned above, the vocabulary contains other classes and properties used to enrich the Environment dimension:

**POI.** Location is modelled with the notion of Point of Interest (POI). The class consists in a simplified, RDFized version of W3C Point of Interest Core specifications<fnref n="7" />. POIs are defined as entities that describe information about locations such as name, category or unique identifier. Each POI consists in a geo:Point subclass that can be associated to a latitude, longitude and a physical radius<fnref n="8" />.

**Activity.** The class consists in a placemark to connect third-party solutions focused on inferring high-level representations of user actions (e.g. ‘driving’, ‘working’, ‘shopping’, etc.).

**radius.** The property specifies the geographic extension of a POI. Value is expressed in metres.

**poi.** The property associates a POI to a prissma:Environment.

**poiLabel.** The property assigns a custom name to a point of interest. The name can be both a URI (e.g. http://dbpedia.org/resource/Harrods) or a literal.

**poiCategory.** The property associates a custom category to a POI (e.g. monument, restaurant, etc.). The vocabulary does not constrain the range of the property in any kind. Hence, both URIs (e.g. http://dbpedia.org/resource/Shopping_mall) and literals are valid. For string literals, a list of place types is presented in RFC 4589⁹.

**motion.** The property associates any given high-level representation of motion to a prissma:Environment.

The third-party terms that have been reused by the PRISSMA vocabulary are listed in Table 1.

**Example.** Figure 3 shows the sample Prism :museumPrism. The Prism styles dbpedia:Museum instances when requested by art-loving users walking in Paris. Fresnel lenses and formats (7-26) are coupled to the PRISSMA context description of lines 30-44 (user interested in art, walking in a location labelled as Paris).

Note that the PRISSMA and Fresnel vocabularies are loosely coupled via the fresnel:purpose property. Hence, if needed, PRISSMA can be fitted into other presentation vocabularies, and can therefore operate with other presentation engines (e.g. by appropriately adapting the prissma:Prism subclassing, and by replacing the fresnel:purpose property with more suitable third-party, vocabulary-specific properties).

<figure><img src="image_5.png" /><figcaption>Figure 3. A sample Prism (prefixes are omitted)</figcaption></figure>

## Creating Prisms: PRISSMA Studio

In a basic PRISSMA scenario, Prisms are created by developers of PRISSMA-equipped applications. Nevertheless, under different use cases, such task can be delegated to dataset publishers, that can therefore specify how triples must be presented under specific contexts. Prisms might be even designed by end users, if PRISSMA-equipped applications supports the addition of third-party Prisms.

Although Prisms can be generated manually, we developed and published online *PRISSMA Studio*<fnref n="10" /> a web application to assist PRISSMA designers in creating Prisms (Figure 4). PRISSMA Studio supports designers in the creation of Fresnel Lenses and Formats, and eases the definition of the associated

<footnote n="7">⁷http://www.w3.org/TR/poi-core</footnote>

<footnote n="8">⁸More refined strategies can be adopted to model a geographical location, but this is out of scope of this work.</footnote>

<footnote n="9">⁹https://www.ietf.org/rfc/rfc4589.txt</footnote>

<footnote n="10">¹⁰Demo: http://bit.ly/prissma-studio
Code: https://github.com/lukostaz/prissma-studio</footnote>
<table><caption>Table 1
Third-party classes and properties reused by the PRISSMA vocabulary.</caption><tr><td>time:Interval</td><td>The class represents a temporal interval.</td></tr><tr><td>ao:time</td><td>The property is used to add a time to an Environment.</td></tr><tr><td>tl:start</td><td>This property refers to the beginning of a time interval. Property value must be a xsd:datetime literal.</td></tr><tr><td>tl:duration</td><td>The property adds the duration of a time interval. Property value must be a xsd:duration literal.</td></tr><tr><td>geo:lat</td><td>The property to add the WGS84 latitude of a SpatialThing (decimal degrees).</td></tr><tr><td>geo:lon</td><td>The property to add the WGS84 longitude of a SpatialThing (decimal degrees).</td></tr><tr><td>ao:activity</td><td>The property links an activity to an Environment (e.g. walking, working, driving). The environmental proximity of a generic real-world entity can trigger different resource representations. The property is therefore used to associate nearby objects to the Environment class.</td></tr><tr><td>foaf:based_near</td><td></td></tr></table>

PRISSMA context. To this regard, the UI allows the creation of user, device, and environment dimensions. For example, defining locations is made easier by a map-based widget for point of interests. Date pickers help in determining time and duration. Multiple literals or URIs can be added in text boxes for describing activities, nearby entities, user interests, and device features. PRISSMA Studio lets designers associate a context to multiple lenses and formats, and the resulting Prism can be downloaded as a turtle file.

Once created, Prisms can be stored on the file system of PRISSMA-equipped mobile devices, where they will be processed by the PRISSMA selection algorithm.

## Prism Selection Algorithm

Before rendering an RDF resource with Fresnel, PRISSMA-equipped applications search the available Prisms and select the better match for the context in which the desired resource is accessed, thus our second research question: *how to select the proper context description at runtime?* The most relevant challenge of this task is the imprecise and incomplete nature of context data, that complicates the matching procedure between declared and sensed contexts, and requires an error-tolerant approach. Context data is riddled by the following issues:

**Ambiguity.** Some RDF Entities and literals used in PRISSMA declarations might not match with the actual context entities. Nevertheless, in some cases entities and literals might be similar.

**Incompleteness.** The authors of PRISSMA context declarations might omit or forget certain properties, when describing a context. Nevertheless, in certain cases the context graph, although topologically different, should still be considered as a valid candidate by the selection algorithm.

**Sensor noise.** Onboard sensors might provide erroneous information that will be part of the actual context graph (Henricksen & Indulska, 2004). This is a well-known problem when determining geographic location

(e.g. weak GPS signal, indoor location, etc).

To overcome such issues, we extended and adapted to RDF the Messmer and Bunke error-tolerant algorithm for finding *optimal* subgraph isomorphisms for labelled, directed graphs (Messmer & Bunke, 1998).

**Example.** The triples in Figure 5a model a user interested in computers (lines 8-9), near to Jack (http://jack.example.org, lines 12-13). The geographic location (lines 16-18) is determined by a (latitude, longitude) couple and by a radius that determines the extension of the area (100m). Figure 5b represents an actual context captured by a mobile device. Such graph is somehow similar to Figure 5a, although presenting some differences in topology and in literal values (e.g. location).

## Definitions

Before describing the adapted algorithm, we remind some useful definitions provided in Messmer (Messmer & Bunke, 1998), adjusting them to our scenario:

**Definition 2 (RDF Graph).** An RDF graph is a set of RDF triples $G = \{(s_1, p_1, o_1) \dots (s_n, p_n, o_n)\} = (V, E)$ where $s_i$ is the subject, $p_i$ the property and $o_i$ the object of each triple $t$. $V$ is the set of labelled vertices and contains the elements $s_i$ and $o_i$, that are entities or literals. $E$ is the set of directed edges and contains all the triple properties $p_i$.

**Definition 3 (Graph Edit Operation).** Given an RDF graph $G = (V, E)$, a graph edit operation $\delta(G)$ is one of the following:

- $v \to v'$, $v \in V, v' \in V$ (substituting an RDF entity or literal)

- $e \to e'$, $e \in E$ (substituting an RDF property)

- $v \to \epsilon$, $v \in V$ (deleting an RDF instance or literal)

- $e \to \epsilon$, $e \in E$ (deleting an RDF property)

- $\epsilon \to e$ (adding an RDF property between existing nodes)

where $\epsilon$ is an empty RDF entity, literal, or property.

These five edit operations are sufficient to transform any
<figure><img src="image_6.png" /><figcaption>Figure 4. Screenshots of PRISSMA Studio: (a) shows general Prism information. Lenses and Formats are defined in (b) and (c). Device information is built in (d), user profile in (e), and environment triples are created in (f).</figcaption></figure>

graph G into a subgraph of any graph $G'$. Note that the algorithm searches for subgraph isomorphisms from a model graph to the input graph, hence there is no need to consider exterior RDF instances or literals in the input graph, i.e. there is no need for a $\epsilon \to v$, $v \in V$ operation.

**Definition 4 (Edited Graph).** Given an RDF graph $G$ and a sequence $\Delta = (\delta_1, \delta_2, \dots, \delta_n)$ of edit operations, the edited graph $\Delta(G) = (\Delta(V), \Delta(E))$ is the graph $\Delta(G) = \delta_n(\dots\delta_1(G))$.

**Definition 5 (Error-Tolerant RDF Subgraph Isomorphism).** Given two RDF graphs $G = (V, E)$ and $G' = (V', E')$, an error-tolerant RDF subgraph isomorphism $f$ from $G$ to $G'$ is a two-tuple $f = (\Delta, f_\Delta)$ where:

- $\Delta$ is a sequence of graph edit operations that transforms $G$ in $\Delta(G)$.

- $f_\Delta$ is an injective function $f_\Delta: \Delta(G) \to V'$ such that $\exists$ a graph isomorphism$^{11}$ from $\Delta(G)$ to a subgraph $S \subseteq G'$.

We now introduce the definition of *cost of error-tolerant subgraph isomorphism*, preceded by the *cost* of an edit operation:

**Definition 6 (Cost of Edit Operation).** Given an edit operation $\delta_i$, the cost of $\delta_i$ is a value $C(\delta_i) \in [0, 1]$.

<footnote n="11">¹¹Definition of graph isomorphism provided in (Messmer & Bunke, 1998).</footnote>
<figure><img src="image_7.png" /><figcaption>Figure 5. A sample Prism with its associated graph-based representation (a), and a sample actual context (b).</figcaption></figure>

The cost $C(\delta_i)$ of an edit operation $\delta_i$ varies according to the type of edit operation (e.g. instance substitution, property deletion, etc.) and the nature of the involved RDF element.

**Definition 7** (Cost of Error-Tolerant RDF Subgraph Isomorphism). Given an error-tolerant RDF subgraph isomorphism $f = (\Delta, f_{\Delta})$, its cost $C(f)$ is defined as the normalized cost of the sequence of edit operations $\Delta = (\delta_1, ..., \delta_n)$, $C(f) = \frac{C(\Delta)}{n} = \frac{\sum_{i=1}^{n} C(\delta_i)}{n}$.

The cost of error-tolerant subgraph isomorphism described in Definition 7 adopts the arithmetic mean to normalize the cost of the sequence of edit operations. Other strategies might be adopted, such as using a weighted mean or the maximum cost in the sequence.

It is evident that there might exist multiple sequences $\Delta$ of edit operations from graph $G$ to graph $G'$, each with a different cost: we are interested in finding the optimal error-tolerant subgraph isomorphism, i.e. the error-tolerant subgraph isomorphism with the least expensive sequence of edit operations. In other words, we want to find the minimum amount of distortion needed to transform a Prism into the actual mobile

context, thus computing their graph edit distance (Riesen, Jiang, & Bunke, 2010):

**Definition 8** (Optimal Error-Tolerant RDF Subgraph Isomorphism). Given the set of error-tolerant subgraph isomorphisms $F = \{f_1, ..., f_n\}$ between two graphs, the optimal error-tolerant subgraph isomorphism $f_{opt}$ is the element of $F$ with cost $C(f_{opt}) = \min_{f_i \in F} C(f_i)$.

## Decomposition

The context-related triples included in each Prism are split in subgraphs and saved in a structure called *decomposition*, a recursive partitioning of a set of RDF models (Prisms). The decomposition algorithm works on the set of Prisms preloaded by the PRISSMA-equipped mobile application. The idea is building the decomposition by detecting and merging common subgraphs: in the decomposition, subgraphs duplicated in different Prisms are collapsed and represented only once, thus providing a compact representation of possible contexts. As remarked by Messmer and Bunke, there exists more than one decomposition for a set of graphs: the adopted
<figure><img src="image_8.png" /><figcaption>Figure 6. A decomposition of context data of :museumPrism showed in Figure 3.</figcaption></figure>

strategy does not provide an optimal decomposition (e.g. in the number of elements), but it is computationally inexpensive compared to other strategies (Messmer & Bunke, 1998). The elements of a decomposition are tuples that include graph patterns sharing the same topology and whose RDF elements have the same classes. Among the decomposition elements, some consist in groups of non-decomposable, atomic graph patterns called *context units*:

**Definition 9 (Context Unit).** A context unit is an RDF graph $U = (V_U, E_U)$ representing atomic context information. A context unit $U$ consists in either a single class, or a single RDF entity, or a single literal, or in a graph that describes an atomic context information.

In the original proposition, Messmer and Bunke deal with graphs with a limited range of discrete values, thus they decompose graphs up to single nodes. We compare more complex structures, hence the need to preserve context units (e.g. we cannot split latitude, longitude, and radius when comparing locations). Thus, different types of context units have been defined, according to the type of context information: Class context units consist in core PRISSMA classes (e.g. prissma:Context, prissma:User, prissma:Environment, and prissma:Device). Class context units are created by a preliminary step, where instances of core PRISSMA classes are substituted by their class. This operation decreases the size of the decomposition without losing information, since the URIs of such core instances are not important for matching purposes. Entity context units are RDF entities, whose classes are not among PRISSMA core classes. Entity context units may be blank nodes. Geo context units represent geographic locations, while Time elements include temporal information. Both Geo and Time context units may be blank nodes. String and Numeric context units are associated to string and numeric

literals. The decomposition is formally defined as follows:

**Definition 10 (Decomposition).** Given a set of Prisms $P = \{P_1, \dots, P_n\}$, the decomposition $D(P)$ is a set of 4-tuple $(G, G', G'', E)$ where:

1. $G, G', G''$ are RDF graphs, with $G', G'' \subset G$

2. $E$ is a set of RDF properties such that $G = G' \cup_E G''$, where $\cup_E$ is the union of $G'$ and $G''$ properties.

3. for each $P_i$ there exists a 4-tuple $(P_i, G', G'', E) \in D(P)$

4. for each 4-tuple $(G, G', G'', E)$ there exists no other 4-tuple $(G_1, G'_1, G''_1, E) \in D(P)$ with $G = G_1$

5. for each 4-tuple $(G, G', G'', E) \in D(P)$

(a) if $G'$ is not a context unit, there exists a 4-tuple $(G_1, G'_1, G''_1, E) \in D(P)$ such that $G' = G_1$

(b) if $G''$ is not a context unit, there exists a 4-tuple $(G_2, G'_2, G''_2, E) \in D(P)$ such that $G'' = G_2$

(c) if $G'$ is a context unit, there exists no 4-tuple $(G_3, G'_3, G''_3, E) \in D(P)$ such that $G' = G_3$

(d) if $G''$ is a context unit, there exists no 4-tuple $(G_4, G'_4, G''_4, E) \in D(P)$ such that $G'' = G_4$

**Example.** Figure 6 shows the decomposition of :walkingInParisArt Lover, the Prism in Figure 3. Uppermost elements are context units: 0 and 4 are “String” context units, 1, 5, and 8 are “Class” context units, and 3 is a “Geo” context unit. Each decomposition elements contains the IDs of the ancestors $(G', G'')$ and the set of connecting RDF properties $E$. Element 10 represents the complete prissma:Context graph.

<table><caption>**Algorithm 1:** decompose(G,D)</caption><thead><tr><th></th><th>Data: a Prism G, the decomposition D</th></tr></thead><tbody><tr><td>1</td><td>Result: The updated decomposition D</td></tr><tr><td>2</td><td>if G not context unit then</td></tr><tr><td>3</td><td>&nbsp;&nbsp;&nbsp;&nbsp;foreach (G<sub>i</sub>, G'<sub>i</sub>, G''<sub>i</sub>, E<sub>i</sub>) do</td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[ if G<sub>i</sub> is a subgraph of G and S<sub>max</sub> smaller than G<sub>i</sub> then</td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[ S<sub>max</sub> = G<sub>i</sub></td></tr><tr><td>6</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if S<sub>max</sub> is isomorphic to G then</td></tr><tr><td>7</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[ exit</td></tr><tr><td>8</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (S<sub>max</sub> = Ø) then</td></tr><tr><td>9</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[ choose subgraph S<sub>max</sub>, priority to PRISSMA properties</td></tr><tr><td>10</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;decompose(S<sub>max</sub>)</td></tr><tr><td>11</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;decompose(G - S<sub>max</sub>)</td></tr><tr><td>12</td><td>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;add (G, S<sub>max</sub>, G - S<sub>max</sub>, E) to D</td></tr></tbody></table>

The recursive function *decompose*() (Algorithm 1) is executed on each Prism G in the decomposition D. The function searches in the decomposition for $S_{max}$, the biggest subgraph of G (lines 3-5): the goal is to determine if there exists a graph pattern in common with the decomposition<fnref n="12" />. If $S_{max}$ is isomorphic<fnref n="12" /> to G, then G is already represented in D and the algorithm stops (lines 6-7). If no subgraph is found, and

<footnote n="12">¹²The graph isomorphism and the exact subgraph isomorphism operations are delegated to off-the-shelf algorithms, such as (Ullmann, 1976) whose description is out of the scope of this work.</footnote>
G can be further decomposed (i.e. it is not a context unit), the procedure chooses $S_{max}$ (line 9) and recursively decomposes it (line 10). The choice of $S_{max}$ is determined by a list of ordered RDF properties, with a priority for PRISSMA background ontology core properties (e.g. **prissma:User**, **prissma:Environment**, **prissma:Device**, etc). This enhances the chances of merging decomposition elements, thus resulting in a more compact structure. The procedure is invoked recursively on $G - S_{max}$, the part of G not yet decomposed (line 11). Finally, $(G, S_{max}, G - S_{max}, E)$ is added to D.

**Example.** Figure 7 shows the step-by-step decomposition of the context graph included in the Prism presented in Figure 5a. Note that the context graph has been pre-processed to replace the instances of core PRISSMA classes (**prissma:Context**, **prissma:User**, and **prissma:Environment**) with their classes (instances of core PRISSMA classes are not relevant for the context selection algorithm). The first cut edge chosen is the core PRISSMA property **prissma:User** (note that core PRISSMA properties have higher priority, line 9 Algorithm 1), so that $S_{max}$ and $G - S_{max}$ are defined as shown in Step 1. The procedure **decompose()** is called recursively on $S_{max}$, thus generating $S_{max}$ and $G - S_{max}$ (Step 2). The algorithm is then performed on $S_{max}$ (Step 2). The latter is a context unit (type "string"), and is therefore added to the decomposition and assigned a unique ID. Conversely, $G - S_{max}$ is added to the decomposition as context unit ("class" type). The algorithm backtracks (Step 3, 4) and decomposes $G - S_{max}$ following the same principle: first, the core property **prissma:Environment** is chosen as cut edge (Step 3). In Step 5 $S_{max}$ is decomposed into $S_{max}$ and $G - S_{max}$, that are both context units (type "entity" and "geo", respectively), and thus added to the decomposition. Note that, once a "geo" context unit is detected, its structure is preserved. Backtracking (Step 6), the algorithm adds to the decomposition $G - S_{max}$, $(:ctxA$, turned into a **prissma:Context** "class" type context unit). Finally, elements 2 and 9 of the decomposition are joined to create element 10, that represents the original Prism context definition.

## Search Algorithm

Every significant context change<fnref n="13" /> detected by the device triggers the search for Prisms that fit the updated context requirements. PRISSMA carries out this operation with an adapted version of Messmer and Bunke online search algorithm (Messmer & Bunke, 1998). The algorithm detects optimal error-tolerant subgraph isomorphisms between the graph of the sensed context and the Prisms stored in the decomposition. The algorithm first computes edit operations between context units in the decomposition *D* and context units of the input graph. Second, it combines such edit operations to obtain optimal error-tolerant subgraph isomorphisms for larger patterns, up to complete Prisms

(Algorithm 3). To avoid combinatorial explosion, the concatenation of error-tolerant subgraph isomorphisms includes only the cheapest error-tolerant graph isomorphisms: this guarantees to find optimal error-tolerant subgraph isomorphisms. Note that because it always chooses the cheapest graph isomorphism, and because it runs on a domain consisting in the entire decomposition structure, the algorithm guarantees to find a global optimum.

Algorithm 2 presents the *search* procedure: first, it finds the error-tolerant subgraph isomorphisms from each context unit *S* of the decomposition *D* to the input context graph $G_I$ and stores them in the list *candidates*(*S*) (lines 1-2). This operation is performed by the *context_unit_matchin*g() function. From line 3 to 12 such error-tolerant subgraph isomorphisms are concatenated to find error-tolerant subgraph isomorphisms for larger graphs, up to Prisms: in line 3 we select the subgraph $S_1$ whose error-tolerant subgraph isomorphism $f_1$ has the minimum cost in *D*. Note that $C(f_1)$ must be lower than a threshold $T \in [0, 1]$. The error-tolerant subgraph isomorphism $f_1$ is removed from *candidates*($S_1$) in line 5 and added to the list *winners*($S_1$), the container of error-tolerant subgraph isomorphism chosen to be combined. If $S_1$ is a Prism, the algorithm has found a result (lines 6-7). Otherwise, we generate error-tolerant subgraph isomorphisms for each subgraph *S* having $S_1$ as ancestor (lines 8-12). Such generation is done with the *combine*() function that concatenates $f_1$ to each $f_2 \in \text{winners}(S_2)$, where $S_2$ is the other ancestor of *S*. If a combination is feasible, the resulting error-tolerant subgraph isomorphism is added to *candidates*(*S*) (line 12).

Algorithm 3 details the *combine*() procedure: first (line 1), the function tests if $f_1$ and $f_2$ do not contain mappings to the same node in $G_I$ (this is necessary because subgraph isomorphisms are injective functions (Messmer & Bunke, 1998)). If this condition is satisfied, an error-tolerant subgraph isomorphism is constructed as a concatenation of the edit operations of $f_1$ and $f_2$ and of the edit operations on the edge between $S_1$ and $S_2$, $\Delta_E$ (line 8). Mappings are chosen among the mappings of $f_1$ and $f_2$ (lines 3-7).

We now discuss in further detail *context_unit_matchin*g(), the function used by the search algorithm to compute error-tolerant subgraph isomorphisms for context units (Algorithm 4). Given a context unit *U* and an input context graph $G_I$, the procedure finds the edit operations from *U* to each context unit of $G_I$ (line 2-3) and stores them as error-tolerant subgraph isomorphisms. Moreover, the deletion of *U* is considered (line 5).

Worst case computational complexity analysis shows that the complexity of the search procedure varies from $O(Lm^n n^2)$ when Prisms in the decomposition are completely different, to

<footnote n="13">¹³The notion of significant context change is scenario-dependent, and it is not investigated in this paper.</footnote>
<figure><img src="image_9.png" /><figcaption>Figure 7. The decomposition() algorithm executed on :PrismaA (triples in Figure 5a). Each step includes the choice of $S_{max}$ (the cut property that connects $S_{max}$ with $G - S_{max}$ is marked in red) and the decomposition (newly added elements are in bold.)</figcaption></figure>
**Algorithm 2: search(G<sub>I</sub>, D)**

**Data:** a Decomposition *D*, a context graph *G*<sub>*I*</sub>
**Result:** the result set *R* containing selectable Prisms
1 **foreach** *S* context unit in *D* do
2   **[** candidates(*S*) = context_unit_matchings(*S*, *G*<sub>*I*</sub>)
3   **while** choose *S*<sub>1</sub> | ∃ *f*<sub>1</sub> ∈ candidates(*S*<sub>1</sub>) with *C*(*f*<sub>1</sub>) minimal in *D* and
   *C*(*f*<sub>1</sub>) ≤ *T* **do**
   4     winners(*S*<sub>1</sub>) = winners(*S*<sub>1</sub>) ∪ {*f*<sub>1</sub>}
   5     candidates(*S*<sub>1</sub>) = candidates(*S*<sub>1</sub>) − {*f*<sub>1</sub>}
   6     **if** *S*<sub>1</sub> is a Prism **then**
   7       **[** *R* = *R* ∪ {*S*<sub>1</sub>} **
   8       **foreach** (*S*, *S*<sub>2</sub>, *E*) ∈ *D* || (*S*, *S*<sub>2</sub>, *S*<sub>1</sub>, *E*) ∈ *D* **do**
   9       **foreach** *f*<sub>2</sub> ∈ winners(*S*<sub>2</sub>) **do**
  10         *f* = combine(*S*<sub>1</sub>, *S*<sub>2</sub>, *E*, *G*<sub>*I*</sub>, *f*<sub>1</sub>, *f*<sub>2</sub>)
  11         **if** *f* ≠ ∅ **then**
  12           **[** candidates(*S*) = candidates(*S*) ∪ {*f*}
  13     **return** *R* **]**

**Algorithm 3: combine()**

**Data:** S<sub>1</sub>, S<sub>2</sub>, E, G<sub>I</sub>, f<sub>1</sub> = (Δ<sub>1</sub>, f<sub>Δ<sub>1</sub></sub>), f<sub>2</sub> = (Δ<sub>2</sub>, f<sub>Δ<sub>2</sub></sub>), Δ<sub>1</sub> = (Δ<sub>V<sub>1</sub></sub>, Δ<sub>E<sub>1</sub></sub>), Δ<sub>2</sub> = (Δ<sub>V<sub>2</sub></sub>, Δ<sub>E<sub>2</sub></sub>)
**Result:** f
1 **if** f<sub>Δ<sub>1</sub></sub>(Δ<sub>V<sub>1</sub></sub>) ∩ f<sub>Δ<sub>2</sub></sub>(Δ<sub>V<sub>2</sub></sub>) ≠ ∅ **then**
2   **[** exit
3 **foreach** v ∈ (Δ<sub>V<sub>1</sub></sub> ∪ Δ<sub>V<sub>2</sub></sub>) **do**
4     **if** v ∈ V<sub>Δ<sub>1</sub></sub> **then**
5       **[** f<sub>Δ<sub>1</sub></sub>(v) = f<sub>Δ<sub>1</sub></sub>(v)
6     **else if** v ∈ V<sub>Δ<sub>2</sub></sub> **then**
7       **[** f<sub>Δ<sub>2</sub></sub>(v) = f<sub>Δ<sub>2</sub></sub>(v)
8   Δ = Δ<sub>1</sub> + Δ<sub>2</sub> + Δ<sub>E</sub>
9   **return** f = (Δ, f<sub>Δ</sub>)
**]**

O(m^n n^2) when Prisms are highly similar (L is the number of Prisms in the decompositions, m the number of vertices of the input context graph and n the number of vertices of each Prism included in a decomposition D made of Prisms with same number of nodes). Hence, the search algorithm is sublinear in the number L of Prisms included in the decomposition (for a detailed theoretical analysis of the computational complexity of the search algorithm, see (Messmer & Bunke, 1998)). This is an important property of the algorithm, since the number of Prisms in the system can be potentially high and unknown a priori.

**Algorithm 4: context_unit_matchings(U, G<sub>I</sub>)**

**Data:** context unit *U*, input context graph *G*<sub>*I*</sub> = (*V*<sub>*I*</sub>, *E*<sub>*I*</sub>)
**Result:** the list of error-tolerant subgraph isomorphisms *F*
1 *F* = ∅
2 **foreach** context unit *U*<sub>*I*</sub> ∈ *G*<sub>*I*</sub> **do**
3   **[** generate an error-tolerant subgraph isomorphism *f* between *U* and *U*<sub>*I*</sub>
4   *F* = *F* ∪ {*f*}
5   *f*' = (Δ', f'<sub>Δ'</sub>) with Δ' = (*v* → *ε*) and f'<sub>Δ'</sub> = ∅
6   *F* = *F* ∪ {*f*'}
7   **return** *F*

<table><caption>Table 2
Cost value ranges associated to graph edit operations presented in Definition 3. Note that the presence of additional properties between two context units is not considered to have an impact on the global cost, and is therefore assigned cost 0.</caption><thead><tr><th>Edit Operation δ</th><th>Cost C(δ)</th></tr></thead><tbody><tr><td>(v, v' "Class")</td><td>0 if URIs match, 1 otherwise</td></tr><tr><td>v → v'</td><td>0 if URIs match, C<sub>topology</sub> ∈ [0, 1] otherwise</td></tr><tr><td>(v, v' "String")</td><td>C<sub>string</sub> ∈ [0, 1]</td></tr><tr><td>(v, v' "Geo")</td><td>C<sub>geo</sub> ∈ [0, 1]</td></tr><tr><td>(v, v' "Time")</td><td>C<sub>time</sub> ∈ [0, 1]</td></tr><tr><td>e → e' (e core property)</td><td>0 if URIs match, 1 otherwise</td></tr><tr><td>(e not core)</td><td>0 if URIs match, C<sub>topology</sub> ∈ [0, 1] otherwise</td></tr><tr><td>v → ε, e → ε</td><td>1 if v is "Class", "Geo", "Time", or e core property. C<sub>topology</sub> ∈ [0, 1] otherwise</td></tr><tr><td>ε → e</td><td>0</td></tr></tbody></table>

## Cost of Edit Operations

Each graph edit operation $\delta$ computed by the Prism selection algorithm is associated to a cost $C(\delta) \in [0, 1]$. Unlike Messmer and Bunke that only consider topological differences and limit to graphs with discrete node values, in our scenario cost functions are influenced by the presence of heterogeneous context dimensions. Table 2 summarizes the values of cost ranges for edit operations.

**Topology.** The algorithm assigns the highest cost $C(\delta) = 1$ to the substitution of “Class” context units, core PRISSMA vocabulary properties (such as *prissma:environment*), and to the deletion of “Class”, “Geo” or “Time” context units. Hence, whenever an input context graph needs such edit operations, the cost of the resulting error-tolerant subgraph isomorphism will be higher than the threshold $T$. The algorithm assigns lower costs for edit operations on non-core properties, and on “Entity” context units (e.g. a missing *foaf:interest* property in the user dimension may not prevent a Prism match). Such cost is determined by the $C_{topology} \in [0, 1]$ parameter. Note that the presence of additional properties between two context units is not considered to affect global cost, and is therefore assigned cost 0.

**Location.** A “Geo” context unit is a subgraph composed by *geo:lat*, *geo:long* and a *prissma:radius* (e.g. context unit 3 in Fig. 7). The cost of the substitution of a location context unit depends on the geographic distance. We first compute the distance *d* of the two points using the Haversine formula. The Haversine equation computes the distance of two points on a sphere, given their latitudes *lat*<sub>1</sub> and *lat*<sub>2</sub>, longitudes *lng*<sub>1</sub> and *lng*<sub>2</sub>, and the Earth radius *r*:

$$d = 2r \arcsin(\sqrt{\sin^2(\frac{\text{lat}_2 - \text{lat}_1}{2}) + \cos(\text{lat}_1) \cos(\text{lat}_2) \sin^2(\frac{\text{lng}_2 - \text{lng}_1}{2})})$$

If *d* is within the declared radius, the edit operation
<figure><img src="image_10.png" /><figcaption>Figure 8. The exponential decay function used to compute the substitution of a geo context unit.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 9. The function used to compute the substitution of a time context unit.</figcaption></figure>

has cost $C(\delta) = 0$. Otherwise, PRISSMA features an exponential decay function to smooth the transition between a perfect match and a mismatch<fnref n="14" /> (Figure 8):

$$C_{geo}(d) = \begin{cases} 0 & \text{if } d < d_{radius} \\ e^{-\frac{d}{\lambda_{geo}}} & \text{if } d > d_{radius} \end{cases}$$

**Time.** Temporal context units include a start timestamp $t_{start}$ and a duration $\Delta_t$ (Figure 2). The cost of the substitution of a temporal pattern is computed to an exponential decay function (Figure 9):

$$C_{time}(t) = \begin{cases} e^{-\frac{t-t_{start}}{\Delta_t}} & \text{if } t < t_{start} \\ 0 & \text{if } t_{start} < t < t_{start} + \Delta_t \\ e^{-\frac{t+t_{start}+\Delta_t}{\Delta_t}} & \text{if } t > t_{start} + \Delta_t \end{cases}$$

**Strings.** The cost $C_{string}$ of substituting a string literal is computed with an approximate string matching strategy, to overcome problems such as spelling variants (to date, the Prism selection algorithm focus only on this string similarity problem). The algorithm adopts the Monge-Elkan distance function (according to Cohen et al. (Cohen, Ravikumar, & Fienberg, 2003) such function outperforms other approaches when dealing with spelling variants, as shown in the "Algorithm Validation" Section of this paper).

In the PRISSMA Vocabulary Section of this paper we claim that the PRISSMA ontology can be refined and extended by

third-party domain specialists. The search algorithm supports any model extensions. Indeed, the above list of edit operation costs is extensible, in case the context model is updated with entities that do not fit the current list.

**Example.** Consider the decomposition of :PrismA in Figure 7 (Step 6). The search() algorithm is given as input the actual context showed in Figure 5b ($G_I = :ctxActual$). Search threshold is set to $T = 0.5$. The search process is explained in Figure 10. The uppermost part of the picture shows the numbered context units included in $G_I$. At step 1, the algorithm computes subgraph isomorphisms from each input context units to every decomposition context unit, i.e. it builds candidates vectors $C$. In the figure, only the least expensive subgraph isomorphisms are shown (the remaining isomorphisms are represented by "...". For instance, context unit 0 has a subgraph isomorphism containing a substitution operation (SUB) with input context unit 14 that costs 0.45 (this is the result of the similarity function between the string "computer" and "computer programming"). The geographical context unit 3 has a substitution cost of 0.21 with input context unit 17. Context units 1, 4, 5, and 8 have least expensive subgraph isomorphisms of cost 0 (a perfect match with some input context unit has been found). The algorithm chooses the decomposition item with the lowest error-tolerant subgraph isomorphism. At step 2, this item is 8 (prissma:Context). The subgraph isomorphism is moved to the winners vector $W$. Since at this stage no descendant of item 8 has elements in winners, the algorithm repeats the same steps for elements with ascending minimum costs. Step 2 shows that the least expensive subgraph isomorphisms for items 1, 4, and 5 are moved to $W$. When working on item 4, the algorithm detects that its descendant 6 whose other ancestor (item 5) has values in $W$. A subgraph isomorphism for 6 is then built, as the concatenations of subgraph isomorphisms of 4, 5, and their combination with the combine() function. The resulting subgraph isomorphism is stored in $C$, with cost=0 (cost is the average of the concatenated isomorphisms costs, Definition 7). At step 3, the $W$ vector of the geo context unit 3 is filled. Since the descendant 7 has both ancestors with elements in their $Ws$, a subgraph isomorphism is created as the concatenation of ancestor $W$ items, and stored in $C$, with cost 0.042. At step 4, the least expensive operation for element 0 is moved to $W$, and it is concatenated into the subgraph isomorphism of element 2, that has average cost 0.15. In step 5, the least cost of 2 is still below $T$, so $W$ is filled up. The other ancestor of descendant 10 has a value in $W$, therefore a subgraph isomorphism for 10 is computed. At step 6 this subgraph isomorphism cost is compared to the threshold $T$. The cost is below $T$, thus, given that 10 represents the complete context :ctxA, the input context matches to :PrismA.

<footnote n="14">¹⁴More refined geospatial matching techniques are out of the scope of this work, e.g. http://linkedgeodata.org/.</footnote>
<figure><img src="image_12.png" /><figcaption>Figure 10. Search algorithm example</figcaption></figure>
Algorithm Validation

We assess the validity of the Prism selection algorithm<sup>15</sup> with different cost functions parameters and similarity thresholds *T*. The main drawback of edit distance-based subgraph matching algorithms is the need for a proper tuning campaign for cost functions parameters, as acknowledged by Messmer and Bunke (Messmer & Bunke, 1998). Such parameters influence the behaviour of cost functions, thus impacting on overall matching results. Hence, we first analyse edit operations in isolation, and we later proceed in assessing the search algorithm on complete contexts. The first analysis evaluates the role of *C<sub>topology</sub>*, and tests the algorithm on matching contexts with missing context units. The second analysis evaluates matching results with different values of *λ<sub>geo</sub>*. The third analysis deals with *λ<sub>time</sub>*. The fourth test compares approximate matching string functions. Finally, in our last test, we put all together, and we assess complete contexts. Each test uses a decomposition including one Prism only. The Prism has been matched against groups of 50 context graphs that have been manually annotated by the authors (half of them have been annotated as positive matches)<sup>15</sup>.

For the *C<sub>topology</sub>* validation, the **prissma:Context**
in the Prism contains a **prissma:User** and a
**prissma:Environment** dimensions. The user has five
distinct **foaf:interest** properties (string literals). The
environment has four distinct **prissma:nearbyEntity**
properties, with entity-type context units (hence, the test
Prism contains 12 context units in total). Positive matches
consist in copies of the decomposed Prism having at most
four missing context units (either **foaf:interest** or
**prissma:nearbyEntity** values). That accounts for 1/3 of
the Prism context units. Figure 11a shows that, if threshold
*T* is at least as high as the cost assigned to a missing unit
cost, *F*<sub>1</sub> score reaches *F*<sub>1</sub> = 0.67 (precision *P* = 0.5, recall
*R* = 1), thus under these conditions the algorithm does not
miss any true matching input context. Only one true positive
is detected if the cost of a missing entity is below *T*, and such
match corresponds to a context identical to the test prism.
In this case the algorithm discards candidate isomorphisms
whose cost is less than *T*, including isomorphisms on single
context units with a deletion operation as candidate with
lowest cost.

Figure 11b shows the validation test results for the lo-
cation decay constant $\lambda_{geo}$. The *prissma:Context* in the
decomposed Prism contains only a *prissma:Environment*
dimension. The environment includes a POI, modelled with
a “Geo” context unit (latitude, longitude, and radius). Posi-
tive matches consist in context graphs with the same topol-
ogy, but with different location values. Location context
units are considered positive match if the distance to the de-
clared radius boundary is at most 10% the radius itself (e.g.
*prissma:radius* = 1 Km, input context is a positive match
up to 1.10 Km, with increasing cost *C*<sub>geo</sub>). Not surprisingly,

steeper exponential decays (higher decay constants) have better precision, but lower recall, as the exponential function decreases faster. For example, with our test configuration, if *T* = 0.3 and *λ<sub>geo</sub>* = 5, we obtain *F*<sub>1</sub> = 0.92 (precision *P* = 0.92 and recall *R* = 0.92), while if *T* = 0.3 and *λ<sub>geo</sub>* = 50, we obtain *F*<sub>1</sub> = 0.68 (precision *P* = 1 and recall *R* = 0.52).

The third test assesses the temporal decay constant $\lambda_{time}$ (Figure 11c). The **prissma:Context** in the decomposed Prism contains only a **prissma:Environment** dimension. The environment includes a **time:Interval** entity, i.e. a “Time” context unit (**tl:start**= “12:00”, and **tl:duration**= 2 hours). Positive matches consist in context graphs with the same topology, but with different time values. Time context units are considered positive matches if i) are contained in the declared time interval, ii) are at most after 10% of the duration from the duration limit, or iii) occur before $t_{start}$, but within a 10% tolerance.

Figure 11d shows the test results of four different string
similarity measures (Jaro, Jaro-Winkler, Monge-Elkan, and
Levenshtein) chosen to match string literals with com-
pound words and spelling variants (note that a thorough
evaluation of these techniques is out of the scope of this
work). The **prissma:Context** in the decomposed Prism
contains only a **prissma:User** dimension. The user in-
cludes a **foaf:interest** property with the string literal
value “computer programming”. Positive matches consist
in context graphs with the same topology, but with different
**foaf:interest** values. Such values are considered positive
matches if the adopted string similarity measure returns a
value *s* such that *T* ≤ 1 − *s*. For instance, the following
values are considered as positive matches: “programming”,
“computer programming environments”, “computer program-
ming languages”, “computer programs”, while values such
as “programs and software” or “computer software devel-
opment” are considered negative matches. Results confirm
surveys such as (Cohen et al., 2003), that show that the Monge-
Elkan distance function outperforms other approaches. Be-
sides spelling variants and compound words, input contexts
and prisms might include semantically similar string literals
(e.g. “jazz” and “music”). In this case, similarity metrics for
spelling variants fall short of providing good results, and se-
mantic similarity measures are needed. In Figure 12 we com-
pare the best performing metric for spelling variants (Monge-
Elkan) with the Wu-Palmer semantic similarity measure im-
plemented in the WS4J WordNet Similarity for Java library¹⁶.
Wu-Palmer computes a similarity score by taking into ac-
count the depths of two synsets in WordNet taxonomies (Wu
& Palmer, 1994). In our test, positive matches consist in
context graphs with the same topology as the only Prism in

<footnote n="15"><sup>15</sup>Binaries, code, test data, and complete evaluation results avail-
able at: http://bit.ly/prissma-project

<sup>16</sup>https://code.google.com/p/ws4j/. The library relies on
Princeton's English WordNet 3.0.</footnote>
the decomposition, but with semantically similar values of
foaf:interest (e.g. “jazz”, “saxophone”, “music”, etc).
As expected, Figure 12a shows that for semantically similar
words, Wu-Palmer clearly outperforms Monge-Elkan (note
that results from T = 0.7 lead to false positives rates above
0.6). Nevertheless, response time assessment in Figure 12b
shows that the semantic similarity metric is one order of mag-
nitude slower. Since string comparison will run on the client-
side, we choose to focus on compound words and spelling
variants only, by adopting the Monge-Elkan similarity metric.

Having validated each edit operation in isolation, we
tested the algorithm with all the dimensions at once (Fig-
ure 13). The prissma:Context in the decomposed Prism
is the sum of the contexts described in the previous
tests. It contains a prissma:User with string literals as
foaf:interest values. The prissma:Environment has
four prissma:nearbyEntity entities, a location expressed
with latitude, longitude, and a radius, and a time validity.
We have positive matches under the conditions previously
described (at most four missing units, at most 10% far from
the location radius edge, at most 10% after the time interval,
Monge-Elkan distance function for strings). We assessed
the algorithm in three different configurations, by relying on
the parameter values that guarantees better F₁ score in the
isolation tests: Figures 13a and 13b show that the algorithm
reaches precision values above 0.8 for all the tested configu-
rations. Besides, the F₁ score plot in Figure 13c shows that,
under our test conditions, raising the threshold *T* above 0.6
does not bring any further benefit.

Note that the task of validating the selection algorithm
strongly depends on the notion of *context similarity*, i.e. it re-
lies on subjective decisions, on the nature of context data, and
on application scenarios. The above validation tests would
be enriched in future work by an acceptability evaluation
campaigns with users of mobile applications equipped with
PRISSMA.

Evaluation

The PRISSMA decomposition and selection algorithms
have been implemented as a Java library¹⁵. The library is
showcased by the PRISSMA Browser¹⁵, a mobile Linked
Data browser enhanced with PRISSMA context-aware adap-
tation.

The first test analyses the decomposition memory consump-
tion (Figure 14). The test measured the decomposition size of
groups of Prisms with a variable number of identical context
units. Groups included 20 Prisms, each containing 10 context
units. Overall, test Prisms accounted for 340 triples. The
percentage of identical context units in each group of Prisms
is progressively increased, ranging from 10% to 100% (where
the latter means that all Prisms in the group are represented
by the same decomposition item).

We assigned an arbitrary size of 30 Bytes to context units

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /><figcaption>Figure 11. Search algorithm validation campaign results (Isolated Context dimensions).</figcaption></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /><figcaption>Figure 12. Semantic String similarities vs Monge-Elkan metric: (a) F₁ score, (b) response time.</figcaption></figure>
<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /><figcaption>**Figure 13.** Search algorithm validation campaign results (complete contexts): Precision/Recall (a), ROC (b), $F_1$ score (c).</figcaption></figure>

(we consider UTF-8 strings with an average length of 30 characters), and 42 Bytes to intermediate decomposition elements (one integer ID, two integer ancestors IDs, and a list of connecting edges. Each edge includes a triple of estimated size 90 characters). The size of PRISSMA decompositions are compared with the retained size of a group of Jena Model<fnref n="17" />, each containing a test Prism (Figure 14b). As expected, with higher common context units percentages, we have lower decomposition memory footprints. Nevertheless, the memory size of PRISSMA decomposition is in the same order of magnitude as the Jena models size.

A series of tests have been run to prove the computational complexity analysis of the search algorithm (Figure 15). The algorithm response time has been tested with the proof-of-concept PRISSMA Browser on a group of Android mobile devices (Google Nexus 4, Google Nexus 10, Samsung Galaxy Mega, and Samsung Galaxy Note). All phones were running Android 4.2.2. Figure 15a shows the relationship between $L$, the number of Prisms in the decomposition, and response time. Prisms in each group are all different (thus testing the worst case decomposition configuration). Prisms contain $n = 10$ context units and the test context to be matched is made of $m = 10$ context units. Five independent runs have been

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /><figcaption>**Figure 14.** Decomposition memory consumption analysis</figcaption></figure>

executed for each group of Prisms, thus computing average response time measurements. Results prove a linear dependency, thus confirming the worst case complexity analysis of the search algorithm for what concerns the number of Prisms $O(L)$. Figure 15b shows how the size of the incoming context graph impacts on response time. In this case, each run varied the size $m$ of input context (ranging from 10 to 50 context units) using a fixed group of $L = 5$ Prisms each made of $n = 2$ context units. Results match computational complexity analysis, thus giving a $O(m^n)$ relationship (experimental setup shown in Figure 15b has $n = 2$, thus giving a $O(m^2)$ relationship). Unlike the number of Prisms, the growth associated to the size of the incoming context graph suggests that the size of the latter must be kept as small as possible, to consistently reduce response time. Finally, in Figure 15c the size $n$ of each Prism has been tested. Five independent test runs assessed response time using an incoming context graph of $m = 50$ context units and a decomposition made of $L = 5$ Prisms. Results confirm the complexity analysis $O(n^2)$. As for the case of incoming context graph, the size of Prisms impacts with a quadratic growth on response time, thus it is important to avoid defining useless context conditions in Prisms to lower response time.

## PRISSMA Browser

PRISSMA Browser¹⁵ is a proof-of-concept, Android Linked Data browser enhanced with PRISSMA context-aware

<footnote n="17">¹⁷http://jena.apache.org/documentation/notes/model-factory.html</footnote>
<figure><img src="image_24.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(b)</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>(c)</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>(b)</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>(c)</figcaption></figure>

<caption>Figure 16. Three screenshots of the PRISSMA Browser Android application. Content and layout in (a) are optimized for tablets, while (b) is optimized for users walking in Paris (see the Prism in Figure 3). Figure (c) shows "night mode" optimized content.</caption>

adaptation, and consists in a modified version of the Webkit-based, open-source Lighting Browser<fnref n="18" />. The browser renders RDF resources according to the sensed context, thus relying on the interplay of PRISSMA and Fresnel, and on the Prism selection algorithm.

A PRISSMA context graph is created at startup and updated only when context changes significantly, to reduce battery drain (e.g. by relying on the Android LocationListener.onLocationChanged<fnref n="19" /> method). The browser contains a user-customizable set of Prisms, associated to a number of RDF classes or resources. Prisms are decomposed with the PRISSMA decomposition algorithm and stored in memory. When an RDF resource is requested, the browser performs an HTTP request and fetches the data. As soon as triples are received from the Web, the current client context is used as input for the PRISSMA selection algorithm over the Prisms decomposition. Once the most suitable Prism is found, the associated Fresnel lenses and formats are extracted and used to render the desired resource in HTML. The example in Figure 16 shows three context-aware HTML representations of the DBpedia RDF entity of the Louvre Museum. Content and layout in Figure 16a are optimized for tablets. Figure 16b provides a smartphone visualization of the

same entity optimized for users walking in Paris (the related Prism is described in Figure 3). In such context users will benefit more from practical informations such as the museum address, metro station, and other information such as opening hours. Figure 16c shows the same visualization, with a dark theme optimized for evening access.

## Conclusions

Extending Fresnel with context awareness favours the sharing and reuse of prisms across applications, does not introduce

<footnote n="18">¹⁸https://github.com/anthonycr/Lightning-Browser</footnote>

<footnote n="19">¹⁹http://developer.android.com/reference/android/location/LocationListener.html</footnote>
new formalisms, and is extensible to domain-specific context
data. Operating on the client side guarantees privacy preser-
vation, because context data does not have to be disclosed to
third-party adaptation servers. Moreover, the decomposition
structure supports incremental updates. Memory consumption
tests show that the decomposition structure reduces memory
usage when Prisms contain repeated subgraphs. Response
time test campaign shows the sublinear dependence on the
number of Prisms in the system.

The main limitation of PRISSMA is the need for proper parametrization of the selection algorithm. This is a well-known issue of strategies based on graph edit distance. Instead of relying on heuristic parameter tuning, future work will investigate methods to choose the best-fitting similarity threshold and similarity metrics parameters according to the sensed context, thus relieving developers from manual tuning. Additional cost functions will be added (e.g. semantic distance between URIs), and we will also investigate how to adapt them to client-side computation (e.g. semantic similarity measures for string literals). Response time comparison with cited state-of-the-art solutions is envisaged, but such task would need to adapt these frameworks to a mobile scenario, since none of the related works is designed to run on mobile devices. Moreover, although some of these works provide a response time evaluation, experimental conditions vary, making the comparison difficult. Future work will also include acceptability evaluation campaigns, by assessing the behaviour of PRISSMA-equipped mobile applications users. Prisms distribution has not been examined yet: PRISSMA might support multiple strategies for discovery, retrieve, and consume Prisms published as Linked Data. For instance, since Prisms are RDF declarations, it could be possible to distribute them on the Web of Data, according to Linked Data principles, thus creating *Linked Presentation-level Metadata*. Ad-hoc presentation metadata repositories might be added to the Linked Data cloud, and PRISSMA-powered applications will discover such context-based presentation metadata at run time, thus giving birth to applications that visualize RDF entities with “filters” created by third parties and associated to given contexts only.

References

Auer, S., Doehring, R., & Dietzold, S. (2010). LESS - Template-Based Syndication and Presentation of Linked Data. In *Proceedings of eswc* (Vol. 6089, p. 211-224). Springer.

Bolchini, C., Curino, C. A., Quintarelli, E., Schreiber, F. A., & Tanca, L. (2007, December). A data-oriented survey of context models. *SIGMOD Rec.*, **36**(4), 19–26. doi: 10.1145/1361348.1361353

Carroll, J. J. (2002). Matching rdf graphs. In *The semantic web: *bāĀtiswc 2002* (pp. 5–15). Springer.

Castano, S., Ferrara, A., Montanelli, S., & Varese, G. (2011). Ontology and instance matching. In *Knowledge-driven multimedia information extraction and ontology evolution* (Vol. 6050, p. 167-195). Springer. doi: 10.1007/978-3-642-20795-2_7

Champin, P.-A. (2009). T4R: Lightweight presentation for the Semantic Web. In *Scripting for the semantic web, workshop at eswc*.

Cohen, W. W., Ravikumar, P. D., & Fienberg, S. E. (2003). A comparison of string distance metrics for name-matching tasks. In *Iiweb* (p. 73-78).

Conte, D., Foggia, P., Sansone, C., & Vento, M. (2004). Thirty years of graph matching in pattern recognition. *IJPRAI*, 265-298.

Dadzie, A.-S., Rowe, M., & Petrelli, D. (2011). Hide the Stack: Toward Usable Linked Data. In *Proceedings of eswc* (Vol. 6643, p. 93-107). Springer. doi: 10.1007/978-3-642-21034-1_7

Dey, A. K. (2001). Understanding and using context. *Personal Ubiquitous Comput.*, 5(1), 4-7. doi: 10.1007/s007790170019

Euzenat, J., & Shvaiko, P. (2007). *Ontology matching*. Springer-Verlag.

Fernéandez, J. M. B., Auer, S., & Garcia, R. (2012). The linked data visualization model. In *Iswc (posters & demos)*.

Gandon, F. (2005). Generating surrogates to make the semantic web intelligible to end-users. *Web Intelligence, IEEE / WIC / ACM International Conference on*, 352-358. doi: http://doi.ieeecomputersociety.org/10.1109/WI.2005.66

Gao, X., Xiao, B., Tao, D., & Li, X. (2010). A survey of graph edit distance. *Pattern Analysis & Applications*, 13(1), 113-129.

Gu, T., Pung, H. K., & Zhang, D. (2005). A service-oriented middleware for building context-aware services. *J. Network and Computer Applications*, 28(1), 1-18. doi: 10.1016/j.jnca.2004.06.002

Gu, T., Pung, H. K., Zhang, D. Q., Pung, H. K., & Zhang, D. Q. (2004). A bayesian approach for dealing with uncertain contexts. In *Proc. of the 2nd international conference on pervasive computing (pervasive 2004)* (Vol. 176).

Henricksen, K., & Indulska, J. (2004). Modelling and using imperfect context information. In *Percom workshops* (p. 33-37).

Huynh, D., Karger, D. R., & Quan, D. (2002). Haystack: A platform for creating, organizing and visualizing information using RDF. In *Semantic web workshop* (Vol. 52).

Kiefer, C., Bernstein, A., & Stocker, M. (2007). The fundamentals of iSPARQL: A virtual triple approach for similarity-based semantic web tasks. In *Proceedings of iswc/aswc* (Vol. 4825, p. 295-309). Springer. doi: 10.1007/978-3-540-76298-0_22

Krummenacher, R., & Strang, T. (2007). Ontology-based context modeling. In *Proceedings of the third workshop on context-aware proactive systems (caps)*.

Messmer, B., & Bunke, H. (1998). A new algorithm for error-tolerant subgraph isomorphism detection. *Pattern Analysis and Machine Intelligence, IEEE Transactions on*, 20(5), 493–504.

Pietriga, E., Bizer, C., Karger, D., & Lee, R. (2006). Fresnel: A browser-independent presentation vocabulary for RDF. In *Proceedings of iswc* (Vol. 4273, p. 158-171). Springer. doi: 10.1007/11926078_12

Quan, D., & Karger, D. R. (2005). Xenon: An RDF stylesheet ontology. In *Proceedings of www*.

Riesen, K., Jiang, X., & Bunke, H. (2010). Exact and inexact graph matching: Methodology and applications. In *Managing and mining graph data* (Vol. 40, p. 217-247). Springer.

Rutledge, L., van Ossenbruggen, J., & Hardman, L. (2005). Making RDF presentable: integrated global and local semantic web browsing. In *Proceedings of www* (p. 199-206).
Schraefel, M. M. C., & Rutledge, L. (2010). User interaction in semantic web research. *Journal of Web Semantics*, 8(4), 375-376.

Ullmann, J. R. (1976). An algorithm for subgraph isomorphism.
*Journal of the ACM (JACM)*, 23(1), 31–42. doi: 10.1145/
321921.321925

Volz, J., Bizer, C., Gaedke, M., & Kobilarov, G. (2009). Discovering and maintaining links on the web of data. In *Proceedings of iswc* (p. 650-665).

Wu, Z., & Palmer, M. (1994). Verbs semantics and lexical selection.
*In Proceedings of the 32nd annual meeting on association for computational linguistics* (pp. 133–138).

Zou, L., Chen, L., Özsu, M. T., & Zhao, D. (2012). Answering pattern match queries in large graph databases via graph embedding.
*The VLDB JournalâťThe International Journal on Very Large Data Bases*, 21(1), 97-120.