Rakebul Hasan
email: hasan.rakebul@inria.fr

Fabien Gandon
email: fabien.gandon@inria.fr

Predicting SPARQL Query Performance

We address the problem of predicting SPARQL query performance. We use machine learning techniques to learn SPARQL query performance from previously executed queries. We show how to model SPARQL queries as feature vectors, and use k -nearest neighbors regression and Support Vector Machine with the nu-SVR kernel to accurately (R 2 value of 0.98526) predict SPARQL query execution time.

Query Performance Prediction

The emerging dataspace of Linked Data presents tremendous potential for largescale data integration over cross domain data to support a new generation of intelligent application. In this context, it increasingly important to develop efficient ways of querying Linked Data. Central to this problem is knowing how a query would behave prior to executing the query. Current generation of SPARQL query cost estimation approaches are based on data statistics and heuristics. Statistics-based approaches have two major drawbacks in the context of Linked Data [START_REF] Tsialiamanis | Heuristics-based query optimisation for SPARQL[END_REF]. First, the statistics (e.g histograms) about the data are often missing in the Linked Data scenario because they are expensive to generate and maintain. Second, due to the graph-based data model and schema-less nature of RDF data, what makes effective statistics for query cost estimation is unclear. Heuristics-based approaches generally do not require any knowledge of underlying data statistics. However, they are based on strong assumptions such as considering queries of certain structure less expensive than others. These assumptions may hold for some RDF datasets and may not hold for others. We take a rather pragmatic approach to SPARQL query cost estimation. We learn SPARQL query performance metrics from already executed queries. Recent work [START_REF] Akdere | Learning-based query performance modeling and prediction[END_REF][START_REF] Ganapathi | Predicting multiple metrics for queries: Better decisions enabled by machine learning[END_REF][START_REF] Gupta | PQR: Predicting query execution times for autonomous workload management[END_REF] in database research shows that database query performance metrics can be accurately predicted without any knowledge of data statistics by applying machine learning techniques on the query logs of already executed queries. Similarly, we apply machine learning techniques to learn SPARQL query performance metrics from already executed queries. We consider query execution time as the query performance metric in this paper.

Modeling SPARQL Query Execution

We predict SPARQL query performance metrics by applying machine learning techniques on previously executed queries. This approach does not require any statistics of the underlying RDF data, which makes it ideal for the Linked Data scenario. We use two types of query features: SPARQL algebra features and graph pattern features. We use frequencies and cardinalities of the SPARQL algebra operators1 , and depth of the algebra expression tree as SPARQL algebra features. Regarding graph patterns features, transforming graph patterns to vec- tor space is not trivial because the space is infinite. To address this, we create a query pattern vector representation relative to the query patterns appearing in the training data. First, we cluster the structurally similar query patterns in the training data into K gp number of clusters. The query pattern in the center of a cluster is the representative of query patterns in that cluster. Second, we represent a query pattern as a K gp dimensional vector where the value of a dimension is the structural similarity between that query pattern and the corresponding cluster center query pattern. To compute the structural similarity between two query patterns, we first construct two graphs from the two query patterns, then compute the approximate graph edit distance -using a suboptimal algorithm [START_REF] Riesen | Approximate graph edit distance computation by means of bipartite graph matching[END_REF] with O n 3 computational complexity -between these two graphs. The structural similarity is the inverse of the approximate edit distance. We use the k -mediods [START_REF] Kaufman | Clustering by means of medoids[END_REF] clustering algorithm to cluster the query patterns of training data. We use k -mediods because it chooses data points as cluster centers and allows using an arbitrary distance function. We use the same suboptimal graph edit distance algorithm as the distance function for k -mediods. Figure 1 shows an example of extracting SPARQL algebra features (left) and graph pattern features (right) from SPARQL query string.

Experiments and Results

We generate 1260 training, 420 validation, and 420 test queries from the 25 DBPSB benchmark query templates [START_REF] Morsey | Dbpedia SPARQL benchmark performance assessment with real queries on real data[END_REF]. To generate queries, we assign randomly selected RDF terms from the DBpedia 3.5.1 dataset to the placeholders in the query templates. We run the queries on a Jena-TDB 1.0.0 triple store loaded with DBpedia 3.5.1 and record their query execution time. We exclude queries which do not return any result (queries from template 2, 16, and 21) and run more than 300 seconds (queries from template 20). We experiment with k -nearest neighbors (k -NN) regression [START_REF] Altman | An introduction to kernel and nearest-neighbor nonparametric regression[END_REF] and Support Vector Machine (SVM) with the nu-SVR kernel for regression [START_REF] Shevade | Improvements to the SMO algorithm for SVM regression[END_REF] to predict query execution time. We achieve an R 2 value of 0.9654 (Figure 2(a)) and a root mean squared error (RMSE) value of 401.7018 (Figure 2(b)) on the test dataset using k -NN (with K gp = 10 and k = 2 selected by cross validation). We achieve an improved R 2 value of 0.98526 (Figure 2(c)) and a lower RMSE value of 262.1869 (Figure 2(d)) using SVM (with K gp = 25 selected by cross validation). This shows that our approach can accurately predict SPARQL query execution time.

Conclusion and Future Work

We present an approach to predict SPARQL query execution time using machine learning techniques. We learn query execution times from already executed queries. This approach can be useful where statistics about the underlying data are unavailable We discuss how to model SPARQL queries as feature vectors, and show highly accurate results. In future, we would like to compare our approach to the existing SPARQL query cost estimation approaches in the context of Linked Data query processing.

Fig. 1 .

 1 Fig. 1. Example of extracting SPARQL feature vector from a SPARQL query.

Fig. 2 .

 2 Fig. 2. Predictions for the test dataset with SPARQL algebra features and graph pattern features using k -NN (Kgp = 10 and k = 2) and SVM (Kgp = 25).

Algebra operators: http://www.w3.org/TR/sparql11-query/#sparqlAlgebra

Acknowledgments: This work is supported by the ANR CONTINT program under the Kolflow project (ANR-2010-CORD-021-02).


Rakebul Hasan
email: hasan.rakebul@inria.fr

Kemele M Endris
email: kemele.endris@inria.fr

Fabien Gandon
email: fabien.gandon@inria.fr

SPARQL Query Result Explanation for Linked Data

In this paper, we present an approach to explain SPARQL query results for Linked Data using why-provenance. We present a nonannotation-based algorithm to generate why-provenance and show its feasibility for Linked Data. We present an explanation-aware federated query processor prototype and show the presentation of our explanations. We present a user study to evaluate the impacts of our explanations. Our study shows that our query result explanations are helpful for end users to understand the result derivations and make trust judgments on the results.

Introduction

As a result of the W3C Linked Open Data Initiative, recently we have seen a rapid growth in publishing data sets on the Semantic Web, in form of RDF data with SPARQL query endpoints. This enables developers to query and integrate disparate Semantic Web data. As argued in [START_REF] Theoharis | On provenance of queries on semantic web data[END_REF][START_REF] Wylot | Tripleprov: Efficient processing of lineage queries in a native rdf store[END_REF], it is essential to provide additional explanations about which source data were used in providing results, how the source data were combined, to enable users understand the result derivations, and validate or invalidate the results.

Within the Semantic Web community, explanations have been studied for Semantic Web applications and OWL entailments. Explanation for SPARQL query results has not been independently studied by the community. However, there have been several works on tracing the origin of query results -e.g. whyprovenance. These attempts are based on the annotation approach (the eager approach) where the underlying data model, the query language, and the query processing engine are re-engineered to compute provenance during the query processing. This is undesirable for the Linked Data scenario as re-engineering the underlying data model, the query language, or the query processor is often not possible from the querying side. Furthermore, previous work on explanations for the Semantic Web does not study how explanations impact the end-users.

To address these problems, we provide SPARQL query result explanations. The main component in an explanation for a query result tuple is its whyprovenance. We propose a non-annotation approach to generate why-provenance for SPARQL query results. We present an explanation-aware federated query processor prototype to show the presentation of our explanations. Finally, we present a user study which evaluates the impacts of SPARQL query result explanations on the end-users.

The structure of the rest of this paper is as follows: in section 2, we present the related work. In section 3, we discuss SPARQL query result explanations, introduce the concept of why-provenance, and present our algorithm to generate why-provenance. In section 5, we present our explanation-aware federated query processor prototype. In section 6, we present a user study to evaluate the impacts of explanations. Finally, we conclude and discuss the future work in section 7.

Related Work

Previous work on explanation in the Semantic Web literature [START_REF] Hasan | A Brief Review of Explanation in the Semantic Web[END_REF] addresses the problems of representing explanation metadata [START_REF] Pinheiro Da Silva | A proof markup language for semantic web services[END_REF], and generating explanations for Semantic Web applications [START_REF] Mcguinness | Explaining semantic web applications[END_REF] and entailments [START_REF] Horridge | Laconic and precise justifications in OWL[END_REF]. SPARQL query result explanation has not be studied in the previous work. Query result provenance has been studied in the database community [START_REF] Cheney | Provenance in databases: Why, how, and where[END_REF] and the Semantic Web community. The previous works on provenance for SPARQL query results are based on transforming the RDF data model and SPARQL query language to relational data model and relational database query language respectively [START_REF] Theoharis | On provenance of queries on semantic web data[END_REF][START_REF] Damásio | Provenance for sparql queries[END_REF], or generation of provenance metadata during the query processing [START_REF] Wylot | Tripleprov: Efficient processing of lineage queries in a native rdf store[END_REF][START_REF] Corby | Kgram versatile inference and query engine for the web of linked data[END_REF]. However, in the Linked Data scenario, we do not have any control over the underlying data model or the query processor. Therefore, re-engineering the underlying data model or query processor is often not possible in the Linked Data scenario. Furthermore, the impacts of explanations on end-users has not been studied in the previous work on explanation in the Semantic Web literature. In the other fields, Lim et al. [START_REF] Lim | Why and why not explanations improve the intelligibility of context-aware intelligent systems[END_REF] studied the impacts of explanations on end-users for context-aware applications. Tintarev and Masthoff [START_REF] Tintarev | Evaluating the effectiveness of explanations for recommender systems[END_REF] studied the effectiveness of explanations for recommender systems.

Explaining SPARQL Query Results

We provide SPARQL query result provenance as query result explanations. More precisely, for a SPARQL query result tuple, we provide its why-provenance as its explanation. Buneman et al. [START_REF] Buneman | Why and where: A characterization of data provenance[END_REF] first introduced the notion of why-provenance for relational databases. Why-provenance captures all the different witnesses for a tuple in the query result. For a query Q and output tuple t, a witness is the sufficient subset of the database records which ensures that the tuple t is in the output. Each witness is a derivation for the output tuple. Theoharis et al. [START_REF] Theoharis | On provenance of queries on semantic web data[END_REF] later adapted why-provenance for RDF and SPARQL. Similar to the relational setting, why-provenance for RDF and SPARQL captures all the different derivations of a tuple in the query result. To illustrate, we use a simple example, containing RDF data about professors and the courses they teach, shown in professors who teach undergraduate level courses and their corresponding email addresses. The first triple pattern ?course :courseType :underGrad in the query Q1 selects the undergraduate level courses. The second triple pattern ?prof :course ?course selects the professors for those undergraduate level courses. The next two triple patterns ?prof :email ?email and ?prof :name ?name selects the email addresses and names of the corresponding professors matched by the two previous triple patterns. The result of the query Q1 (under set semantics) executed on the RDF data containing the triples in Figure 1 is shown on the right in Listing 1.1. The why-provenance for the result tuple (Prof. A, a@email.edu) is {{t14, t5, t2, t3}, {t13, t4, t2, t3}}. Each inner set in why-provenance represents a derivation involving the triples in the inner set. This means that the result tuple (Prof. A, a@email.edu) can be derived in two different ways according to Q1. The first one by using the triples t14, t5, t2, and t3. The second one by using the triples t13, t4, t2, and t3. The why-provenance for the result tuple (Prof. B, b@email.edu) on the other hand has one derivation: {{t15, t11, t10, t9}}. Please not that we are using the triple identifiers only for presentation purpose. The original data model containing the triples shown in Figure 1 is not changedi.e. we do not annotate the RDF triples. We use the RDF triples as they are in the original data source.

Algorithm for Generating Why-Provenance

In this section, we present our non-annotation approach to generate why-provenance for SPARQL query results. We currently do not support SPARQL queries with sub-queries, FILTER (NOT) EXISTS, MINUS, property paths, and aggregates. The GenerateWhyProvenace procedure shown in Algorithm 1 generates whyprovenance for an RDF model M, a SPARQL query Q, and a result tuple t.

The RDF model M can be an RDF dataset or a SPARQL endpoint on which the SPARQL query Q is solved and the result tuple t is produced. At line 2

Algorithm 1 Why-provenance algorithm.

1: procedure GenerateWhyProvenace(M,Q,t) 2:

Q ′ ← P rovenanceQuery(Q, t) 3: I ← Q ′ (M ) 4: E ← AlgebricExpression(Q) 5:
W ← DerivationsF romQuery(M, E, I) 6:

return W 7: end procedure of Algorithm 1, we first re-write the original query to a provenance query by adding the tuple t as a solution binding using the SPARQL 1.1 VALUES construct, and projecting all the variables. The result set of the provenance query provides us all the variable bindings on the RDF data for the solution tuple t. Each tuple (row) in the result set of the provenance query represent a derivation for the solution tuple t. The main idea behind our algorithm is to extract why-Algorithm 2 Procedure for creating the provenance query.

1: procedure ProvenanceQuery(Q,t) 2: Q ′ ← AddV alueBindings(Q ′ , t) 3: Q ′′ ← P rojectAllV ariables(Q ′ ) 4:
return Q ′′ 5: end procedure provenance triples from the triple patterns in the original query by replacing the variables in the triple patterns by the corresponding values from each tuple (row) of result of the provenance query. At line 3 of Algorithm 1, we execute the rewritten query. At line 4, we convert the original SPARQL query Q to SPARQL algebraic expression for ease of query parsing and manipulation. At line 5, the DerivationsFromQuery procedure extracts the derivations. Algorithm 2 shows the ProvenanceQuery procedure to re-write the original query to a provenance query. Line 2 adds the result tuple t as a solution binding using the SPARQL 1.1 VALUES construct. Line 3 modifies the query to projects all the variables in the query.

Algorithm 3 shows the DerivationsFromQuery procedure to extract the derivations given the RDF model M, the SPARQL algebraic expression E, and the provenance query results I. Lines 3-20 iterate through all the tuples of I, extracts provenance triples corresponding to each tuple, and stores them in a set of a sets D. We assume that basic a graph pattern in a SPARQL query is not repeated. We use a hash table, BP, to flag which basic graph pattern (BGP) is examined for a tuple in I to extract provenance triples. Lines 4-6 initialize the hash table by setting False for each BPG, meaning none of the basic graph Algorithm 3 Procedure for extracting derivations from a query.

1: procedure DerivationsFromQuery(M,E,I ) 2: D ← ∅ 3:
for each tuple in I do 4:

for each bgp in E do 5:

BP [bgp] ← F alse 6:

end for 7:

T ← ∅ 8:

if hasU nion(E) or hasJoin(E) or hasLef tJoin(E) then 9:

for each operator in E do 10:

T 1 ← T riplesF orOperator(M, operator, tuple, BP ) 11:

if T 1 = ∅ then 12:

T ← T ∪ T 1 13:

end if 14:

end for 15: else 16:

bgp ← GetT heBGP (E) 17:

T ← T riplesF romBGP (M, bgp, tuple, BP ) 18:

end if 19: D ← D ∪ {T } 20:
end for 21:

return D 22: end procedure patterns is examined for the current tuple in I at this point. If a query has just one BGP, we extract the provenance triples from that BGP (lines 15-18) for a tuple in I and store the provenance triples in set T. If a query has more than one BGP, i.e. if the algebraic expression has the union or the join or the left-join operator, we extract the provenance triples from the operand BGPs of each of the operators and store the provenance triples in set T (lines 7-14) for a tuple in I. We only extract provenance triples for a BGP once at this stage -using the hash table BP as flags for BGPs to keep trace of which BGP has been used so far to extract provenance triples. Finally line 19 does a union of the triples extracted for a tuple in I, stored in set T, as an element (shown by braces around T at line 19) with the set of sets D and assigns the result of the union to D. When we go out of the loop started at line 3, D contains all the derivations we extracted. We return the set of sets D at line 21. Each element in D is a set representing a derivation for the result tuple. Algorithm 4 shows the TriplesForOperator procedure which extracts provenance triples from the operands of an operator. Lines 3-4 get the left and the right BGPs for the operator Op. As we are only restricted to SPARQL queries without sub-queries, the operands are always BGPs. Lines 5-7 extract provenance triples from the left BGP L if provenance triples have not been extracted from L yet, and assigns them to the set P. Lines 8-11 extract provenance triples from the right BGP R, stored in the set T, if provenance triples have not been extracted from R yet, and assigns the union of P and T to P. At line 12, we return the set P which Algorithm 4 Procedure for extracting triples from operands of an operator.

1: procedure TriplesForOperator(M,Op,Tup,BP ) 2:

P ← ∅ 3: L ← GetLef tBGP (Op) 4:
R ← GetRightBGP (Op) 5:

if BP [L] = F alse then 6:

P ← T riplesF romBGP (M, L, T up, BP ) 7:

end if 8:

if BP [R] = F alse then 9:

T ← T riplesF romBGP (M, R, T up, BP ) 10:

P ← P ∪ T 11:
end if 12:

return P 13: end procedure contains all the provenance triples extracted from the left and the right BGPs of the operator Op. The TriplesFromBGP procedure calls at line 6 and line 8 check if all the triples extracted from the BGPs exist in the RDF model M by sending SPARQL ASK queries with each extracted triples. This means that a BGP which was an operand of a SPARQL UNION or OPTIONAL operator would contribute to the provenance triples only if it matches against the RDF model M. Algorithm 5 shows the TriplesFromBGP procedure which does this. Lines Algorithm 5 Procedure for extracting triples from a basic graph patter. return T 14: end procedure 3-11 iterate through the triple patterns in the BGP and extracts the triples. At line 4 we replace the variables of a triple pattern by the corresponding values in the tuple Tup, where Tup is a tuple from the result of the re-written provenance query. Lines 5-6 first check if the extracted triple is valid by sending an ASK query with this triple to the RDF model M, then if it's a valid triple we take the triple and store it in the set T. If the triple is not valid (does not exist in M ), we set the flag for the BGP to true and return an empty set (lines 7-9). At line 10, we go out of the loop started at line 3, and set the flag for the BGP to true. Finally at line 11 we return the set of extracted provenance triples.

Performance Evaluation of the Algorithm

We implement our algorithm using Jena-ARQ API 3 . We evaluate our algorithm using the DBPSB benchmark [START_REF] Morsey | Dbpedia SPARQL benchmark performance assessment with real queries on real data[END_REF] queries on a Jena-TDB (version triple store [START_REF] Owens | Clustered TDB: A clustered triple store for Jena[END_REF]. DBPSB includes 25 query templates which cover most commonly used SPARQL query features in the queries sent to DBpedia4 . We generate our benchmark queries from these query templates. We allow Jena-TDB to use 16 GB of memory. We execute all the queries in a commodity server machine with a 4 core Intel Xeon 2.53 GHz CPU, 48 GB system RAM, and Linux 2.6.32 operating system. As the RDF dataset, we use the DBpedia 3.5.1 dataset with 100% scaling factor -provided by the DBPSB benchmark framework. To generate benchmark queries, we assign randomly selected RDF terms from the RDF dataset to the placeholders in the DBPSB query templates. We generate 1 query for each template resulting total 25 queries. Before executing the queries, we restart the triple store to clear the caches. Then we execute the 25 queries and along with the why-provenance algorithm for all the result tuples once in our warm-up phase. Then we execute each query and the why-provenance algorithm for all the result tuples of each query 5 times. We report the average execution time and average provenance generation time for all result tuples (PGT) for each query, both in milliseconds (ms). We specify a 300 second timeout for a query execution. Queries belonging to templates 2, 16, 20, and 21 did not finish executing within the 300 seconds time limit, and hence we do not report them.

Query Execution and Provenance Generation

Table 1 shows the number for results (#RES), query executing time (QET), provenance generation time for all result tuples (PGT), and provenance generation time per result tuple (PGTPR) for DBPSB queries. PGTs for queries with long execution times and large number of results (queries 6, 8, 10, 14, 22, 24, and 25) are very high. This is not surprising because for each result tuple of a query, we execute the original query with the result tuple as a variable-value binding. Database literature already discusses this issue [START_REF] Cheney | Provenance in databases: Why, how, and where[END_REF]. Generally speaking, non-annotation approaches compute provenance only when it is needed, by examining the source data and the output data. This requires sophisticated computations involving the source data and the output data. This means each individual tuple in the output data has to be examined separately to compute their provenance, and hence time required for generating provenance for all the result tuples for a query is high. However, in contrast to the annotation approaches (as in [START_REF] Wylot | Tripleprov: Efficient processing of lineage queries in a native rdf store[END_REF]), our approach does not affect the query execution time. In addition, our goal is to provide provenance as query result explanations. We only need provenance for the result tuple for which the explanation is asked. Therefore, provenance generation time per result tuple (PGTPR) is the interesting measure for us. PGTPR for all the queries are low, ranging from 0.001 ms to 85.8 ms. Even for the long running queries, PGTPR values are low. This is because we add the variable-value binding to the original query to compute provenance, which makes the query simpler to solve for the query processor.

An Explanation-Aware Federated Query Processor

We developed a prototype system for federated query processing with explanation features. Users can ask for explanation for each query result tuple in our system. We implement a virtual integration-based federated query processor. The first step for our federated query processing is selecting the data sources by sending SPARQL ASK queries with each triple pattern. Next, we split the original query to sub-queries, sequentially send them to the relevant data sources (nested loop join), and combine the result in the local federator. Each sub-query is a CONSTRUCT SPARQL query which returns a set of matched triples for its triple patterns. We create a local virtual graph combining the resulted triples from all the sub-queries, then locally solve the original query on this virtual graph using Jena-ARQ. We borrow the idea of CONSTRUCT sub-queries from Corese-DQP [START_REF] Gaignard | Distributed knowledge sharing and production through collaborative e-Science platforms[END_REF]. We also implement the common federated query processing concepts of exclusive triple pattern groups and bound join proposed in [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF]. We provide a user interface to enable users to configure SPARQL endpoints as data sources, and submit queries. Furthermore, users can ask for explanation for each query result tuple from the user interface. We provide three types of information in an explanation. We show the why-provenance triples, which data source each triple in the why-provenance comes from, and which triple pattern of the original query each triple in the why-provenance matches. Figure 2 shows an example of a query result explanation. We generate the why-provenance triples using the algorithm we presented in section 3.1 on the local virtual RDF graph. We keep two additional indexes in the federated query processor to keep trace of which data source each triple comes from, and which triple pattern each triple matches. These two indexes allow us to provide the information on data sources and matched triple patterns in the explanations.

Evaluation of the Impacts of Explanations

We conducted a user study to investigate the impact of query result explanations. Our study is similar to the user study conducted by Lim et al. [START_REF] Lim | Why and why not explanations improve the intelligibility of context-aware intelligent systems[END_REF] to examine effectiveness of different types of explanations for context-aware intelligent systems. The questionnaire for our study consists of three sections: learning section, reasoning section, and survey section. Furthermore, we have two cases: with explanation and without explanation. A participant is randomly assigned to the case of "with explanation" or "without explanation".

In the learning section, participants were given a high-level overview of our query processor and an example SPARQL query with a result tuple to help them learn how the federated query processor works. Participants for the "with explanation" case additionally received the explanation of the result tuple for the example query (as shown in Figure 2). In the reasoning section, participants were given the same SPARQL query as in the learning section, but a different result tuple along with the some triples contained in two data sources (DBpedia5 and LinkedMDB6 ). Then we first ask the participants to select the relevant data sources for each triple pattern in the query. Next, we ask the participants to select the source triples (why-provenance triples) from the two data sources which contributed to the result tuple. Then we ask the participants to rate their confidence on their answer choices for the data source selection and the source triple selection questions. The choices for confidence rating were very low, low, medium, high, and very high. The questions in the reasoning section help us analyze how the users understand the result derivation process and if the explanation provided in the learning section have any impact on their understanding. In the survey section of our study, we ask the participants if explanations help users to understand the result derivation and to make trust judgments on the results. Furthermore, we ask them which types of information they think are helpful in an explanation for understanding and making trust judgments. The questions in the survey section help us understand how the participants feel about the system and its explanation features.

The query we used is a query to find the British movies with American actors. The result tuple includes URIs for a film and an actor. Part of the query is solved in LinkedMDB (finding the British movies) and part of it is solved in DBpedia (finding birth places of the actors). In the query result tuple, we intentionally do not provide natural language descriptions. Instead we provide URIs from LinkedMDB -which are numeric resource URIs -for the actor and the film. This is to make sure that participants are not using their background knowledge about movies and actors in their answers. For the data source selection and source triple selection questions, we provide small subsets of DBpedia triples (11 triples) and LinkedMDB triples (13 triples). We used Google Forms 7 for the questionnaires and Google App Engine 8 to randomize the selection of two cases -"with explanation" or "without explanation". We invited the member of our laboratory 9 (via our mailing list), the members of Semantic Web Interest Group 10 (via their mailing list), and the followers of Twitter hashtags #Seman-ticWeb, #RDF, and #SPARQL. 11 participants took part in the study. There were 6 participants for the "with explanation" case and 5 participants for the "without explanation" case. There were 8 male participants and 3 female participants. The ages of the participants range from 22 to 65. All the participants had knowledge of RDF and SPARQL. The questionnaire and the responses of the participants are available online 11 .

Results of the Study

We analyze the ability of the participants to apply their understanding of the system by computing the number of fully correct, partially correct, and incorrect answers for the data source selection and the source triple selection questions in the reasoning section. If a participant selects all the correct choices for an answer, we consider it as fully correct. If a participant selects all the correct choices but also selects some extraneous choices, we consider the answer as partially correct. If a participant's choices for an answer do not contain all the correct choices, we consider it as incorrect. In addition, if a participant selected all choices given for the source triple selection question, we consider the answer as incorrect to avoid guessing. For the data source selection question, we had 4 questions for 4 triple patterns in the query. We count the number of participants who provided fully correct answers, partially correct answers, and incorrect answers for each of these 4 questions. Then we take the average of the counts for the fully correct answers, the average of the counts for the partially correct answers, and the average of the counts for the incorrect answers. These averages represent the average number of participants into the three answer categories categories -fully correct, partially correct, and incorrect -for the data source selection question as a whole. We compute these averages separately for both the "with explanation" and "without explanation" cases and compute the percentages of participants in the three answer categories for the two cases from these average. Figure 3(a) shows the percentage of participants with fully correct, partially 11 http://ns.inria.fr/ratio4ta/sqe/ correct, and incorrect answers when the explanation is given and when the explanation is not given for the data source selection question. The results are very similar for both "with explanation" and "without explanation" cases. Majority of the participants understood how data source selection works for our federated query processor system when the explanation was given ((79.17%) and also when the explanation was not given (80.0%). Therefore the impact of explanations for source selection understanding is not clear from our study. For the source triple selection question, we had two questions for the two data sources we used. We compute the percentages of participants in the fully correct, partially correct, and incorrect answer categories for the "with explanation" and "without explanation" cases using the same method as the data source selection question. Figure 3(b) shows the percentage of participants with fully correct, partially correct, and incorrect answers when the explanation is given and when the explanation is not given for the source triple selection question. More participants provided correct answers when the explanation was give (75% for "with explanation", 20% for "without explanation"). Furthermore, more participants provide incorrect answers when the explanation was not given (16.67% for "with explanation", 60% for "without explanation"). This clearly shows that participants who were given explanations understood better which triples contributed to the result from the two data sources. The final question in the reasoning section asks participants to rate their confidence level about the answers for the data source selection question and the source triple selection question. Figure 4 shows the confidence level of the participants about their answers. 50.0% of participants with explanation rate their confidence as very high whereas none of participants without explanation rate very high. 33.33% of participants with explanation rate their confidence as high whereas 80% of participants without explanation rate high. This shows that participants with explanation are more confident on their answers -as many of them answered "very high" or "high". For the survey section, we ask the participants if explanations are helpful to understand the query result derivation, and if explanations are helpful to make trust judgments on the query result. If a participant answered "yes", he/she was also asked what kind of information he/she found helpful. Figure 5(a) shows the percentage of participants who answered explanations are helpful or unhelpful for understanding the query result derivation. Majority of the partic- ipants (81.81) responded that explanations are helpful for understanding the query result derivation. Only 18.18% of the participants answered that explanations are unhelpful for understanding the query result derivation -none of these participants were given explanations. Figure 5(b) shows the percentage of participants who answered explanations are helpful or unhelpful to make trust judgments on the query result. Again, Majority of the participants (total 81.81%) responded that explanations are helpful to make trust judgments on the query result. Only 18.18% of the participants answered that explanations are unhelpful to make trust judgments on the query result. This shows that majority of the survey participants feel that explanations are helpful to understand query result derivations and to make trust judgments on query results. Figure 6(a) shows the participants who found information on data source, triple pattern(s), and why-provenance triples helpful for understanding the query result derivation. Please note that only the answers from participants who answered "yes"

shown in Figure 5(a) are considered. Out of 9 participants who answered "yes", 77.78% responded that the data source related information was helpful, 77.78% responded that the triple pattern(s) related information was helpful, and 55.55% responded that the provenance triple related information was helpful. However, our analysis on source selection question responses (Figure 3(b)) shows that the explanation helped participants significantly improve their correctness on selecting the provenance triples. Therefore, it is hard to explain why only 22.22% with explanation responded that the provenance triple related information was helpful. One possible reason could be that when they were not given the explanation, they felt the need for explanation with provenance triple (hence 33.33% for without explanation). But when they were given the explanation, they were not aware that the provenance triple related information helped them to have a better understanding. Figure 6(b) shows the participants who found information on data source, triple pattern(s), and why-provenance triples helpful to make trust judgments. Again only the answers from participants who answered "yes" shown in Figure 5(b) are considered. Out of 9 participants who answered "yes", 55.55% responded that the data source related information was helpful, 44.44% responded that the triple pattern(s) related information was helpful, and 55.55% responded that the provenance triple related information was helpful. Again, it is interesting to notice that participants who were not given the explanation felt the need for provenance triples related information. This analysis shown in Figure 6 shows that participants found data source and triple pattern(s) related information helpful for understanding the query result derivation, but have less stronger feeling about provenance triples related information for understanding query result derivations. For making trust judgments, participants do not have as strong opinions, but majority of them feel that data source and provenance triple related information are helpful.

Conclusion and Future Work

In this paper, we present an approach to explain SPARQL query results for Linked Data. We present a non-annotation approach to generate why-provenance -the main component of an explanation -and show its feasibility for common Linked Data queries. We present an explanation-aware federated query processor prototype and show the presentation of our explanations. Finally, our user study to evaluate the impacts of explanations shows that our query result explanations are helpful for end users to understand the result derivations and make trust judgments on the results.

In the future work, we would like to extend our algorithm to generate howprovenance, which explain how a result tuple was derived with the details of the operations performed in the derivation. Furthermore, we would like to conduct the user study with more participants. Finally, we would like to represent our explanations in RDF using explanation vocabularies such as Ratio4TA [START_REF] Hasan | Generating and summarizing explanations for linked data[END_REF].

Fig- ure 1 .

 1 We use identifiers for each triple for presentation purpose in this paper. Consider the SPARQL query Q1 shown in Listing 1.1, which asks for all the

Fig. 1 .

 1 Fig. 1. Example RDF triples.

Fig. 2 .

 2 Fig. 2. Example of a query result explanation.

Fig. 3 .

 3 Fig. 3. Participants' response about data source selection and source triple selection.

Fig. 4 .

 4 Fig. 4. Participants' confidence level about their answers.

Fig. 5 .

 5 Fig. 5. Percentage of participants who answered explanations are helpful or unhelpful.

Fig. 6 .

 6 Fig. 6. Participants who found different types of information in the explanation helpful.

Table 1 .

 1 Query execution and provenance generation times for DBPSB queries.

	Query #RES QET (ms) PGT (ms) PGTPR (ms)
	1	4	25	12.2	3.05
	3	1	75	65.6	65.6
	4	2	8495.6	8.4	4.2
	5	13	78	102.6	7.89
	6	3238	785	428.2	0.13
	7	21	4.2	57.8	2.75
	8	60447	7392.4	1035.4	0.017
	9	4	1156.2	341.2	85.3
	10	2933	6506.8	164828	56.2
	11	1	0.4	0.01	0.01
	12	1	18.4	43.8	43.8
	13	2	0.4	0.4	0.2
	14	4137	604.6	7999.6	1.93
	15	38	925.6	0.2	0.005
	17	82	20.6	0.6	0.007
	18	34	0.6	0.2	0.006
	19	2	0.4	0.002	0.001
	22 82298	7424.4	405456.4	4.927
	23	1	16.6	17.8	17.8
	24 134968	5729	1700.4	0.013
	25 47696	1683.4 1036758.2	21.737

http://jena.apache.org/

http://dbpedia.org

http://dbpedia.org/

http://linkedmdb.org/

http://www.google.com/google-d-s/createforms.html

https://appengine.google.com/

http://wimmics.inria.fr/, https://glc.i3s.unice.fr/

http://www.w3.org/2001/sw/interest/

Acknowledgments: This work is supported by the ANR CONTINT program under the Kolflow project (ANR-2010-CORD-021-02).


Amira Zaylaa
email: amira.zaylaa@inserm.fr

Jean-Marc Girault
email: jean-marc.girault@univ-tours.fr

Jamal Charara
email: jcharara@ul.edu.lb

Unbiased Recurrence Plot Quantification Of Chaotic Dynamic Systems By Eliminating Sojourn Points

Keywords: Chaotic systems and signals, Recurrence Plot, m-Pattern Recurrence Plot, Derivative-Based Recurrence Plot, Sojourn points

come

Unbiased recurrence plot quantification of chaotic dynamic systems by eliminating sojourn points

I. INTRODUCTION

Recurrence plots (RPs) are popular nonlinear tools for featuring recurring patterns in chaotic systems and signals, thanks to their simple use [START_REF] Takens | Dynamical Systems and Turbulence[END_REF], [START_REF] Eckmann | Recurrence plots of dynamical system[END_REF]. Such representation, enables to visualize in 2-Dimension, the recurrences of D-dimensional patterns. This could be achieved by computing a distance norm between two neighbouring points in d-dimensional embedded space, or between d-embedded signals, at two different instants of time. Based on the knowledge of the time-series, merely, two preliminary steps are required to reconstruct the RP: the first is looking the d-dimension of the embedded system out, while the second is looking the time-delay out between dsignals that ensures their independence. The previous steps were well-known as Taken's theorem [START_REF] Takens | Dynamical Systems and Turbulence[END_REF], [START_REF] Eckmann | Recurrence plots of dynamical system[END_REF]. One could wonder if this heavy procedure could be simplified, as the core information is solely present in the time-series. A certain number of researchers investigated the possibility of directly working on the original time-series i.e. in d =1. However, the simplified assumption have biased the RP representation and its corresponding recurrence quantification analysis (RQA) [START_REF] Marwan | Recurrence-plot-based measures of complexity and their application to heart-rate-variability data[END_REF]. This drawback have triggered the presence of false recurrences (or sojourn points) which were, for instance, identified by N. Marwan [START_REF] Marwan | Recurrence-plot-based measures of complexity and their application to heart-rate-variability data[END_REF]. The correct analysis of recurrences from timeseries is accompanied with sojourn points and is based probably on embedding dimensions [START_REF] Marwan | Recurrence-plot-based measures of complexity and their application to heart-rate-variability data[END_REF], [START_REF] Zbilut | Detecting Deterministic Signals In Exceptionally Noisy Environments Using Cross-Recurrence Quantification[END_REF], [START_REF] Packed | Geometry from a time series[END_REF]. One could wonder about the optimal embedding dimension, which removes sufficiently false recurrences to obtain unbiased recurrence quantification. A question could flush to minds: Are there another methods capable of supplying unbiased quantification?

To answer the previous question, we aimed to correctly remove false recurrence points, in order to obtain unbiased RQA. We proposed to compare four techniques, to obtain unbiased recurrence quantification. We worked on RP (without embedding) and (RP 2 ) with fixed embedding dimension (d=2). Then we worked on what we called Derivative-Based Recurrence Plot (RP 3 ) and m-time Pattern Recurrence Plot (RP 4 ). Through this work, the sine and triangular waves were considered for illustration. To mimic chaotic biomedical systems we worked on the time-series derived from the logistic map.

The originality of the proposed work lies behind the fact that techniques permitting unbiased quantification of RP, could be investigated regardless of the degrees of freedom of the dynamic system.

II. NONLINEAR ANALYSIS METHODS

A. Recurrence Plots and Sojourn Points

In order to illustrate the recurrence test on a single time series we introduced some simulations and reported them in Fig. 1. Fig. 1 represented a schema of (a) a sine wave, x(t), its time delayed version, y(t)=x(t + T/4), their circular phase space (x(t) versus y(t)), (b) a sine wave, x(t), its derivative, ẋ(t), their circular phase space (x(t) versus ẋ(t) ), (c) a triangular wave x(t), its time delayed version y(t)=x(t + T/4), their eight shaped rotated-square phase space and (d) a triangular wave x(t), its derivative ẋ(t), demisquare phase space.

To vividly understand how the recurrence test works out, recall that RP is a two-dimensional squared matrix with black and white dots and two time-axes, where each black dot at the coordinates (i,j) represents a recurrence of the system's state X i with another state Y j . It is expressed, for a fixed embedding dimension d and threshold r, as :

RP = Θ(r -∥X i -Y j ∥), X i ∈ R d , (1)
where X i ∈ R d stands for the point in phase space at which the system is situated at time i, Θ (•) is the Heaviside function, ∥ • ∥ the L ∞ norm and i, j =1,...,Nd +1.

For any chaotic system with a single observation, one can reconstruct the RP for Y j =X i+τ based on two parameters, the time delay 'τ ' and d. Denote RP by RP 1 (without embedding).

Fig. 1 (a) pointed out the recurrence of the points denoted 1 and 3 (existing within the same slice). The problem was that 1's were true recurrences, however, 3 was a sojourn point. To eliminate the number of sojourn points a commonly used technique consisted in increasing the embedding dimension. We shortly denoted this throughout the paper by RP 2 . The recurrence test [START_REF] Marwan | Recurrence-plot-based measures of complexity and their application to heart-rate-variability data[END_REF], [START_REF] Zbilut | Detecting Deterministic Signals In Exceptionally Noisy Environments Using Cross-Recurrence Quantification[END_REF], [START_REF] Packed | Geometry from a time series[END_REF] involved in RP 2 was computed with Y j =X i+τ . To schematize this, RP 2 was used in Fig. 1 (a). Within this figure and recalling that point 3 was not a true recurrence, points denoted as 1's in signal x(t), corresponding to points denoted as 2's and marked as red circles in the delayed signal y = x(t+τ ), have existed within the slice. But, the point denoted as 3 and marked as a red x(t), corresponded to a point denoted as 4 in signal y(t). Since this point was not situated within the slice, it was not considered in the test. In this manner, it was vividly evident that 3 was a sojourn point. Note that RP 2 in Fig. 1 (a) and (b) corresponding to d =2 with y = x(t + τ ), were similar for two different signals.

Instead of finding what was the best time delay τ and embedding dimension d that permit to reconstruct a topologically acceptable phase space and an unbiased RP, another approach discussed in the following section could be used.

B. Derivative-Based Recurrence Plot

The proposed Derivative-Based Recurrence Plots are based on the derivative of time-series. This approach neither requires searching for the time-delay nor embedding dimension. It was denoted by RP 3 for Y j = Ẋi . Note that in Fig. 1 (a) and (c), the following equation: x(t + τ )= ẋ(t) was verified, whereas, in (b) and (d) was not, i.e., x(t + τ ) ̸ =ẋ(t). In Fig. 1 (c) and (d), points denoted by 1 occurred at the same level in the signal ẋ(t) and possessed the same value, however, point 3 which corresponded to point 4 in signal ẋ(t) occurred at different level. This vividly evidenced that point 3 was a sojourn point and should not be counted in the recurrence test.

Note that, though ẋ(t) of the sine and triangular signals differ, the same quantification process was applicable. In Fig. 1 (c) and (d) the RP 3 were in general made up of five diagonal structures, but as a zoom in, they started at different instants of time, this evidenced that the technique was sensitive to the derivative of the signal solely.

Although this method requires two signals, it is not an embedding process, since the embedding process requires the minimization of the mutual information, while RP 3 requires the minimization of the number of sojourn points.

C. m-Pattern Recurrence Plot

Based on the previous method, it was essential to have additional information on the recurrence test. For that, m-Pattern Recurrence Plot was introduced. Instead of considering a point-point recurrence computation, a multi-pattern could be involved, for instance, 2-point to 2 point or 3-point to 3-point computation until m-point-m-point computation. Denoted mathematically by RP 4 , it was given by Eq. 1 for Y j =X j .

III. RESULTS

A. Application To Sine Wave

A sine wave of 200 points has been simulated. Moreover, in RP 2 , producing unbiased quantification required few primer computations. To select the optimal values of d and τ , we have solved the optimization problem given by Eq. 2, through minimizing the cost function J(θ k ).

θ * k = arg min θ (J(θ k )), (2)
where θ k =(d k , τ k ) was the kth embedding dimension and time delay to be optimized and J was the number of false recurrence points defined as follows:

J(θ k )=%CrossDiagonal = N a=amin aP (a) N i,j=1 RP (θ k ) × 100, (3)
where P(a) was the number of cross-diagonal lines of length a, a min the minimum length of cross-diagonal line [START_REF] Nguyen | Automated Quantification of the Synchrogram by Recurrence Plot Analysis[END_REF] and θ k =1 in RP 3 and RP 4 . optimization. Then τ was tested in the range 0 τ 55. This led to an optimized range rather than a unique value.

Note that the time-delay proposed in Taken's theorem, was verified in 2 (bottom) to be (τ = T/4) i.e. within the optimal range obtained. The solution of the minimization of the mutual information was a special case of the solution obtained by the minimization of the false recurrence function J. Consequently, it was not necessary to chose another value, i.e. (τ ̸ = T/4).

After applying the discussed techniques, the results were depicted in Fig. 3 (left) as followed: RP 1 , RP 2 for (τ =T/4), RP 3 for m=1 and RP 4 for m=2. RP 1 in Fig. 3 constituted few diagonal and cross-diagonal lines presenting periodicity. RP 2 revealed that the cross-diagonal lines, which were present in the first image, have vanished totally. However, the size of the diamond-shaped patterns have decreased as compared to RP 1 . RP 3 manifested how the cross-diagonal lines, which were present in RP, have totally vanished. However, it showed a drawback which was the loss of the junction points, presence of gaps and a doubling in the number of diamond-shaped patterns. RP 4 , showed how the cross-diagonal lines have vanished when increasing the wavelength. Although sojourn points have approximately vanished, few points lying along the cross-diagonal were left intact. This was a sort of a drawback of RP 4 . As a global visual evidence, sojourn points have been eliminated using RP 2 , RP 3 and RP 4 .

B. Application To Logistic Map

As a convention and in order to mimic dynamical biomedical systems, the four techniques were applied on the chaotic mathematical system, known as the Logistic Map. The timeseries derived from the logistic map was represented by Fig. 3 (top right) and defined as:

x n+1 = b * x n * (1 -x n ), (4)
where b was 2.8 and n, the number of points, was 200. Fig. 3 (right) represented the RP, RP 2 for τ =4 , RP 3 for m=1 and finally RP 4 for pattern m=2. RP 1 of the Logistic timeseries x showed various small diagonal and cross-diagonal lines reflecting the chaotic nature of the simulated system. RP 2 revealed that almost all cross-diagonal lines have vanished, still, significant vertical lines and patterns have vanished too. RP 3 showed how the cross-diagonal lines which were present in the reference image of the RP have vanished. However, the other small structures remained unchanged. The RP 4 , revealed that once the wavelength increased, the cross-diagonal lines vanished, even though, there were non-negligible loss in the vertical information as compared to RP 3 . So sojourn points were well-eliminated by means of RP 3 and RP 4 of the Logistic signal.

To quantify the number of sojourn points, DET [START_REF] Gao | On the structures and quantification of recurrence plots[END_REF] and J cost-function were calculated. Table I represented the %DET values along the diagonal and J(% Cross-Diagonal) of values in RP 1 , RP 2 , RP 3 and RP 4 of a Sine and logistic signal. For a sine wave, %DET and J values of RP 1 were close. This was in synchronization with the theory, provided that, RP 1 was uniform. However, %DET of RP 2 , which was 80 %, has increased as compared to RP 1 and J which was 20%, have decreased. Specifically, 10% out of 50.3% cross-diagonal lines were detected, i.e., 5.0 % of sojourn points remained on the cross-diagonal lines and 90 % were eliminated. Moreover by RP 3 , J was 24%, i.e.,12 % out of 50% or 6.0 % of sojourn points remained and 76% were eliminated. Then J by RP 4 was 29%, i.e., 14.5% out of 50.3% remained and 71% were dropped out. RP 4 was capable of eliminating the sojourn point 5% more than RP 3 . This evidenced that mathematically the unbiased RP 4 quantification was the most sensitive.

For the logistic signal, from 63% by RP 1 to 61% by RP 2 the number of the points detected along the diagonal decreased, this could be due to some large diagonal lines that were transformed into separate discrete points; this was reflected in the increased number of points detected along the crossdiagonal lines. The trivial comparison of the cross-diagonal values with respect to the detected points forming the crossdiagonal lines obtained through the standard RP 1 shows that (i) 14.4% out of 37% cross-diagonal points were detected in RP 2 , (ii) 13.3% out of 37% cross-diagonal points were detected in RP 3 , however, in (iii) 13% out of 37% cross-diagonal points were detected in RP 4 .

Note that RP 2 was comparable with RP 3 . However, the calculation of RP 3 and RP 4 was time-effective and required no a prior information. They were directly manipulated from the time series, being in this work either the sine signal (or triangular signal) and the Logistic signal. As an overall, they did not drop out vertical or diagonal information as RP 2 . Moreover, even though RP 3 was advantageous over RP 4 in eliminating sojourn points, some true recurring points (junction points) were lost. This offsets that the technique had overestimated the quantification of sojourn points. Nevertheless, RP 4 was advantageous over RP 3 in the sense that all the diagonal information were preserved, anyhow, most of the sojourn points were eliminated. As well as RP 4 was better than RP 2 , such that no constraints were implicated, it preserved the size of junctions. There was always a compromise between the small cross-diagonal lines and junction points.

IV. CONCLUSIONS It was possible throughout this work to establish unbiased quantification by eliminating sojourn points. These unbiased quantifications, have provided a tool for a clean RP which permits better analysis of chaotic dynamic systems. As a future prospect, we ought to validate the findings on real biomedical signals.

Fig. 1 .

 1 Fig. 1. Schematic illustration of Phase Space, Recurrence test computation of (a),(b) a sine and triangular waves x(t) and y = x(t + τ ) and (c),(d) a sine and triangular waves x(t) and y= ẋ(t).

Fig. 2 .

 2 Fig. 2. The cost-function and optimization test of the embedding dimension and time delay.

Fig. 2 (

 2 top) represented the cost function as a function of d, while holding τ fixed to quarter the period, and (bottom) the cost function as a function of the time delay while holding d fixed to 2. As inferred from Fig. 2 (top), the first zero-crossing of J occurred at d =2 . Consequently, d =2was used in the

Fig. 3 .

 3 Fig. 3. RP, RP 2 , RP 3 and RP 4 of (left) the simulated sine wave and (right) the Logistic signal.

TABLE I SOJOURN

 I POINT QUANTIFICATION BY %DET AND J OF RP 1 ,RP 2 ,RP 3 AND RP 4 OF A SINE AND LOGISTIC TIME SERIES.

	Dynamic System	Sine Wave	Logistic Map
	Determinism (% Number	Diagonal	Cross-	Diagonal	Cross-
	Of Points Remaining On		Diagonal (J)		Diagonal (J)
	RP1	49.7%	50.3%	63%	37%
	RP2	39.8%	5.0%	38.4%	5.3%
	RP3	37.8%	6.0%	40.3%	4.9%
	RP4	35.8%	7.3%	40.5%	4.8%

ACKNOWLEDGEMENTS

The authors are grateful to the Lebanese University and National Council for Scientific Research in Lebanon for supporting this work.