Thomas Minier
email: thomas.minier@univ-nantes.fr

Hala Skaf-Molli

Pascal Molli
email: pascal.molli@univ-nantes.fr

SaGe: Web Preemption for Public SPARQL Query Services

To provide stable and responsive public SPARQL query services, data providers enforce quotas on server usage. Queries which exceed these quotas are interrupted and deliver partial results. Such interruption is not an issue if it is possible to resume queries execution afterward. Unfortunately, there is no preemption model for the Web that allows for suspending and resuming SPARQL queries. In this paper, we propose SaGe: a SPARQL query engine based on Web preemption. SaGe allows SPARQL queries to be suspended by the Web server after a fixed time quantum and resumed upon client request. Web preemption is tractable only if its cost in time is negligible compared to the time quantum. The challenge is to support the full SPARQL query language while keeping the cost of preemption negligible. Experimental results demonstrate that SaGe outperforms existing SPARQL query processing approaches by several orders of magnitude in term of the average total query execution time and the time for first results.

INTRODUCTION

Context and motivation: Following the Linked Open Data principles (LOD), data providers published billions of RDF triples [START_REF] Bizer | Linked Data -The Story So Far[END_REF][START_REF] Schmachtenberg | Adoption of the Linked Data Best Practices in Different Topical Domains[END_REF]. However, providing a public service that allows anyone to execute any SPARQL query at any time is still an open issue. As public SPARQL query services are exposed to an unpredictable load of arbitrary SPARQL queries, the challenge is to ensure that the service remains available despite variation in terms of the arrival rate of queries and resources required to process queries.

To overcome this problem, most public LOD providers enforce a fair use service policy based on quotas [START_REF] Buil Aranda | SPARQL Web-Querying Infrastructure: Ready for Action?[END_REF]. According to DBpedia administrators:"A Fair Use Policy is in place in order to provide a stable and responsive endpoint for the community." 1 The public DBpedia SPARQL endpoint 2 Fair Use Policy prevents the execution of SPARQL longer than 120 seconds or that return more than 10000 results, with a limit of 50 concurrent connections and 100 requests per second per IP address. Quotas aim to share fairly server resources among Web clients. Quotas on communications limit the arrival rate of queries per IP. Quotas on space prevent one query to consume all the memory of the server. Quotas on time aim to avoid the convoy phenomenon [START_REF] Blasgen | The Convoy Phenomenon[END_REF], i.e., a long-running query will slow down a short-running one, in analogy with a truck on a single-lane road that creates a convoy of cars. The main drawback of quotas is that interrupted queries can only deliver partial results, as they cannot be resumed. This is a serious limitation for Linked Data consumers, that want to execute long-running queries [START_REF] Polleres | A More Decentralized Vision for Linked Data[END_REF].

Related works: Existing approaches address this issue by decomposing SPARQL queries into subqueries that can be executed under the quotas and produce complete results [START_REF] Buil Aranda | Strategies for Executing Federated Queries in SPARQL1.1[END_REF]. Finding such decomposition is hard in the general case, as quotas can be different from one server to another, both in terms of values and nature [START_REF] Buil Aranda | Strategies for Executing Federated Queries in SPARQL1.1[END_REF]. The Linked Data Fragments (LDF) approach [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF] tackles this issue by restricting the SPARQL operators supported by the server. For example, in the Triple Pattern Fragments (TPF) approach [START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], a TPF server only evaluates triple patterns. However, LDF approaches generate a large number of subqueries and substantial data transfer.

Approach and Contributions: We believe that the issue related to time quotas is not interrupting a query, but the impossibility for the client to resume the query execution afterwards. In this paper, we propose SaGe, a SPARQL query engine based on Web preemption. Web preemption is the capacity of a Web server to suspend a running query after a time quantum with the intention to resume it later. When suspended, the state S i of the query is returned to the Web client. Then, the client can resume query execution by sending S i back to the Web server.

Web preemption adds an overhead for the Web server to suspend the running query and resume the next waiting query. Consequently, the main scientific challenge here is to keep this overhead marginal whatever the running queries, to ensure good query execution performance. The contributions of this paper are as follows:

• We define and formalize a Web preemption model that allows to suspend and resume SPARQL queries.

• We define a set of preemptable query operators for which we bound the complexity of suspending and resuming of these operation, both in time and space. This allows to build a preemptive Web server that supports a large fragment of the SPARQL query language.

• We propose SaGe, a SPARQL query engine, composed of a preemptive Web server and a smart Web client that allows executing full SPARQL queries 3 .

• We compare the performance of the SaGe engine with existing approaches used for hosting public SPARQL services. Experimental results demonstrate that SaGe outperforms existing approaches 3 The SaGe software and a demonstration are available at http://sage.univ-nantes.fr PREFIX dbo : < h t t p : / / d b p e d i a . o r g / o n t o l o g y / > PREFIX r d f s : < h t t p : / / www. w3 . o r g / 2 0 0 0 / 0 1 / r d f -schema # > SELECT ? a c t o r ? name ? b i r t h P l a c e WHERE { ? a c t o r a dbo : A c t o r ; r d f s : l a b e l ? name ; dbo : b i r t h P l a c e ? c i t y . ? c i t y a dbo : C i t y ; r d f s : l a b e l ? b i r t h P l a c e . } by several orders of magnitude in term of the average total query execution time and the time for first results.

This paper is organized as follows. Section 2 summarizes related works. Section 3 defines the Web preemption execution model and details the SaGe server and the SaGe client. Section 4 presents our experimental results. Finally, conclusions and future work are outlined in Section 5.

RELATED WORKS

SPARQL endpoints. SPARQL endpoints follow the SPARQL protocol 4 , which "describes a means for conveying SPARQL queries and updates to a SPARQL processing service and returning the results via HTTP to the entity that requested them". Without quotas, SPARQL endpoints execute queries using a First-Come First-Served (FCFS) execution policy [START_REF] Fife | R68-47 Computer Scheduling Methods and Their Countermeasures[END_REF]. Thus, by design, they can suffer from convoy effect [START_REF] Blasgen | The Convoy Phenomenon[END_REF]: one long-running query occupies the server resources and prevents other queries from executing, leading to long waiting time and degraded average completion time for queries.

To prevent convoy effect and ensure a fair sharing of resources among end-users, most SPARQL endpoints configure quotas on their servers. They mainly restrict the arrival rate per IP address and limit the execution time of queries. Restricting the arrival rate allows end-users to retry later, however, limiting the execution time leads some queries to deliver only partial results. To illustrate, consider the SPARQL query Q 1 of Figure 1. Without any quota, the total number of results of Q 1 is 35 215, however, when executed against the DBpedia SPARQL endpoint, we found only 10 000 results out of 35 215 5 .

Delivering partial results is a serious limitation for a public SPARQL service. In SaGe, we deliver complete results whatever the query. In some way, quotas interrupt queries without giving the possibility to resume their execution. SaGe also interrupts queries, but allows data consumers to resume their execution later on.

Decomposing queries and restricting server interfaces. Evaluation strategies [START_REF] Buil Aranda | Strategies for Executing Federated Queries in SPARQL1.1[END_REF] have been studied for federated SPARQL queries evaluated under quotas. Queries are decomposed into a set of subqueries that can be fully executed under quotas. The main drawbacks of these strategies are: (i) They need to know which quotas are configured. Knowing all quotas that a data provider can implement is not always possible. (ii) They can only be applied to a specific class of SPARQL queries, strongly bounded SPARQL queries, to ensure complete and correct evaluation results.

The Linked Data Fragments (LDF) [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF] restrict the server interface to a fragment of the SPARQL algebra, to reduce the complexity of queries evaluated by the server. LDF servers are no more compliant with the W3C SPARQL protocol, and SPARQL query processing is distributed between smart clients and LDF servers. Hartig et al. [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF] formalized this approach using Linked Data Fragment machines (LDFMs). The Triple Pattern Fragments (TPF) approach [START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF] is one implementation of LDF where the server only evaluates paginated triple pattern queries. As paginated triple pattern queries can be evaluated in bounded time [START_REF] Heling | Querying Large Knowledge Graphs over Triple Pattern Fragments: An Empirical Study[END_REF], the server does not suffer from the convoy effect. However, as joins are performed on the client, the intensive transfer of intermediate results leads to poor SPARQL query execution performance. For example, the evaluation of the query Q 1 , of Figure 1, using the TPF approach generates 507156 subqueries and transfers 2Gb of intermediate results in more than 2 hours. The Bindings-Restricted Triple Pattern Fragments (BrTPF) approach [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF] improves the TPF approach by using the bind-join algorithm [START_REF] Haas | Optimizing Queries Across Diverse Data Sources[END_REF] to reduce transferred data but joins still executed by the client. In this paper, we explore how Web preemption allows the server to execute a larger fragment of the SPARQL algebra, including joins, without generating convoy effects. Processing joins on server side allow to drastically reduce transferred data between client and server and improve significantly performance. For example, SaGe executes the query Q 1 of Figure 1 in less than 53s, with 553 requests and 2.1Mb transferred.

Preemption and Web preemption. FCFS scheduling policies and the convoy effect [START_REF] Blasgen | The Convoy Phenomenon[END_REF] have been heavily studied in operating systems. In a system where the duration of tasks vary, a longrunning task can block all other tasks, deteriorating the average completion time for all tasks. The Round-Robin (RR) algorithm [START_REF] Kleinrock | Analysis of A time-shared processor[END_REF] provides a fair allocation of CPU between tasks, avoids convoy effect, reduces the waiting time and provides good responsiveness. RR runs a task for a given time quantum, then suspends it and switches to the next task. It repeatedly does so until all tasks are finished. The value of this time quantum is critical for performance: when too high, RR behaves like FCFS with the same issues, and when its too low, the overhead of context switching dominates the overall performance. The action of suspending a task with the intention of resuming it later is called preemption. In public Web servers, preemption is already provided by the operating systems, but only between running tasks, excluding those waiting in the server's queue. If we want to build a fully preemptive Web server, we need to consider the queries sent to the server as the tasks and the Web server as the resource that tasks competed to get access to. In this paper, we explore how preemption can be defined at the Web level to execute SPARQL queries.

WEB PREEMPTION APPROACH

We define Web preemption as the capacity of a Web server to suspend a running query after a fixed quantum of time and resume the next waiting query. When suspended, partial results and the state of the suspended query S i are returned to the Web client 6 . The client can resume query execution by sending S i back to the Web server. Compared to a First-Come First-Served (FCFS) scheduling policy, Web preemption provides a fair allocation of Web server resources across queries, a better average query completion time per query and a better time for first results [START_REF] Anderson | Operating Systems: Principles and Practice[END_REF]. To illustrate, consider three SPARQL queries Q 1 , Q 2 , and Q 3 submitted concurrently by three different Web clients. Q 1 , Q 2 , Q 3 execution times are respectively 60s, 5s and 5s. Figure 2 presents a possible execution of these queries with a FCFS policy on the first line. In this case, the throughput of FCFS is 3 70 = 0.042 queries per second, the average completion time per query is 60+65+70 3 = 65s and the average time for first results is also 65s. The second line describes the execution of Q 1 -Q 3 using Web preemption, with a time quantum of 30s. We consider a preemption overhead of 3s (10% of the quantum). In this case, the throughput is 3 76 = 0.039 query per second but the average completion time per query is 76+38+43 3 = 52.3s and the average time for first results is approximately 30+38+43 3 = 37s. If the quantum is set to 60s, then Web preemption is equivalent to FCFS. If the quantum is too low, then the throughput and the average completion time are deteriorated.

FCFS | 0 | 60 | 65 | 70 Q 1 Q 2 Q 3 Web preemption | 0 | 30 | 33 | 38 | 43 | 46 | 76 Q 1 Q 2 Q 3 Q 1 Figure 2: First-Come First-
Consequently, the challenges with Web preemption are to bound the preemption overhead in time and space and determine the time quantum to amortize the overhead.

Web Preemption Model

We consider a preemptive Web server, hosting RDF datasets, and a smart Web client, that evaluates SPARQL queries using the server. For the sake of simplicity, we only consider read-only queries7 in this paper. The server has a pool of server workers parameterized with a fixed time quantum. Workers are in charge of queries execution. The server has also a query queue to store incoming queries when all workers are busy. We consider an infinite population of clients, a finite server queue and a finite number of Web workers.

The preemptive Web server suspends and resumes queries after the time quantum. A running query Q i is represented by its physical query execution plan, denoted P Q i . Suspending the execution of Q i is an operation applied on P Q i that produces a saved state S i ; Suspend(P Q i ) = S i . Resuming the execution of a query Q i is the inverse operation, it takes S i as parameter and restores the physical query execution plan in its suspended state. Therefore, the preemption is correct if Resume(Suspend(

P Q i )) = P Q i .
Figure 3 presents possible states of a query. The transitions are executed either by the Web server or by the client.

The Web server accepts, in its waiting queue, Web requests containing either SPARQL queries Q i , or suspended queries S i . If a worker is available, it picks a query in the waiting queue. For Q i , the worker produces a physical query execution plan P Q i using the optimize-then-execute [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] paradigm and starts its execution for the time quantum. For S i , the server resumes the execution of Q i . The time to produce or resume the physical query execution plan for a query is not deducted from the quantum.

If a query terminates before the time quantum, then results are returned to the Web client. If the time quantum is exhausted and the query is still running, then the Suspend operation is triggered, producing a state S i which is returned to the Web client with partial results. The time to suspend the query is not deducted from the quantum. Finally, the Web client is free to continue the query execution by sending S i back to the Web server.

The main source of overhead in this model is the time and space complexity of the Suspend and Resume operations, i.e., time to stop and save the running query followed by the time to resume the next waiting query. Our objective is to bound these complexities such that they depend only on the query complexity, i.e., the number of operations in the query plan. Consequently, the problem is to determine which physical query plans P Q i have a preemption overhead bounded in O(|Q |), where |Q | denotes the number of operators in the expression tree of P Q i .

Suspending and Resuming Physical Query Execution Plans

The Suspend operation is applied to a running physical query execution plan P Q i . It is obtained from the logical query execution plan of Q i by selecting physical operators that implement operators in the logical plan [START_REF] Garcia-Molina | Database systems -the complete book[END_REF]. A running P Q i can be represented as an expression tree of physical operators where each physical operator has a state, i.e., all internal data structures allocated by the operator. Suspending a plan P Q i requires to traverse the expression tree of the plan and save the state of each physical operator. To illustrate, consider the execution of query Q 2 in Figure 4a. The state of P Q 2 can be saved as described in Figure 4b: the state of the Scan operator is represented by the id of the last triple read t i , the state of the Index Loop Join operator is represented by mappings pulled from the previous operator and the state of the inner scan of tp 1 .

Suspending and resuming a physical query execution plan raise several major issues.

Suspending physical operators in constant time. Bounding the time complexity of Suspend(P Q i ) to O(|Q i |) requires to save PREFIX schema : < h t t p : / / schema . o r g / c o n t e n t S i z e / > PREFIX g r : < h t t p : / / p u r l . o r g / g o o d r e l a t i o n s / > SELECT DISTINCT ? vo ? v1 WHERE { ? v0 g r : i n c l u d e s ? v1 . # t p 1 ? v1 schema : c o n t e n t S i z e ? v3 . # t p 2 } (a) SPARQL query Q 2 , from the Waterloo SPARQL Diversity Test suite benchmark [START_REF] Aluç | Diversified Stress Testing of RDF Data Management Systems[END_REF] A SaGe page

Mappings

Saved state

π ?v0, ?v1 µ c = { ?v0 → wm:Offer81505, ?v1 → wm:Product11, ?v3 → "4355" } Index Loop join µ c = { ?v1 → wm:Product12, ?v3 → "4356" } Index Scan ⟦tp 2 ⟧ D t i = 224 s o u r c e Index Scan ⟦µ c (tp 1 )⟧ D t i = 2 i n n e r
?v0 → wm:Offer79386 ?v1 → wm:Product10014 ?v0 → wm:Offer81506 ?v1 → wm:Product10066 the state of all physical operators in constant time. However, some physical operators need to materialize data, i.e., build collections of mappings collected from other operators to perform their actions. We call these operators full-mappings operators, in opposition to mapping-at-a-time operators that only need to consume one mapping at a time from child operators 8 . Saving the state of fullmappings operators cannot be done in constant time. To overcome this problem, we distribute operators between a SaGe server and a SaGe smart client as follows:

• Mapping-at-a-time operators are suitable for Web preemption, so they are supported by the SaGe server. These operators are a subset of CoreSPARQL [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF], composed of Triple Patterns, AND, UNION, FILTER and SELECT. We explain how to implement these operators server-side in Section 3.3. • Full-mappings operators do not support Web preemption, so they are implemented in the SaGe smart client. These operators are: OPTIONAL, SERVICE, ORDER BY, GROUP BY, DIS-TINCT, MINUS, FILTER EXIST and aggregations (COUNT, AVG, SUM, MIN, MAX). We explain how to implement these operators in the smart client in Section 3.4. As proposed in LDF [START_REF] Hartig | A Formal Framework for Comparing Linked Data Fragments[END_REF][START_REF] Verborgh | Triple Pattern Fragments: A low-cost knowledge graph interface for the Web[END_REF], the collaboration of the SaGe smart client and the SaGe server allows to support full SPARQL queries. This only concerns operators of the SaGe server. To solve this issue, we follow the iterator model [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF][START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF]. In this model, operators are connected in a pipeline, where they are chained together in a pull-fashion, such as one iterator pulls solution mappings from its predecessor(s) to produce results.

Saving consistent states of the physical query plan. Some physical query operators have critical sections and cannot be interrupted until exiting those sections. Saving the physical plan in an inconsistent state leads to incorrect preemption. In other words, we could have Resume(Suspend(P Q i )) P Q i . To solve this issue, we have to detail, for each physical operator supported by the SaGe server, where are located critical sections and estimate if the waiting time for exiting the critical section is acceptable.

Resuming physical operators in constant time. Reading a saved plan as the one presented in Figure 4b should be in O(|Q |). The Index Scan ⟦tp 2 ⟧ D has been suspended after reading the triple with id = 224. Resuming the scan requires that the access to the triple with id ≥ 224 is in constant time. This can be achieved with adequate indexes. To solve this issue, we have to define clearly for each physical operator what are the requirements on backend to bound the overhead of resuming.

The SaGe Preemptable Server

The SaGe server supports Triple Patterns, AND, UNION, FILTER and SELECT operators. The logical and physical query plans are builds thanks to the optimize-then-execute [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] paradigm. The main issues here are the cost of the Suspend and Resume operations on the physical plan and how to interrupt physical operators.

To support preemption, we extend classical iterators to preemptable iterators, formalized in Definition 3.1. As iterators are connected in a pipeline, we consider that each iterator is also responsible for recursively stopping, saving and resuming its predecessors.

Definition 3.1 (Preemptable iterator).

A preemptable iterator is an iterator that supports, in addition to the classic Open, GetNext and Close methods [START_REF] Graefe | The Volcano Optimizer Generator: Extensibility and Efficient Search[END_REF], the following methods:

• Stop: interrupts the iterator and its predecessor(s). Stop waits for all non interruptible sections to complete. • Save: serializes the current state of the iterator and its predecessor(s) to produce a saved state. • Load: reloads the iterator and its predecessor(s) from a saved state. Algorithm 1 presents the implementation of the Suspend and Resume functions for a pipeline of preemptable query iterators. Suspend simply stops and saves recursively each iterator in the pipeline and Resume reloads the pipeline in the suspended state using a serialized state. To illustrate, consider the SaGe page of Figure 4b. This page contains the plan that evaluates the SPARQL query Q 2 of size |Q 2 | = 4, using index loop joins [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF]. The evaluation of tp 2 has been preempted after scanning 224 solution mappings. The index loop join with tp 1 has been preempted after scanning two triples from the inner loop.

In the following, we review SPARQL operators implemented by the SaGe server as preemptable query iterators. We modify the regular implementations of these operators to include non interruptible section when needed. Operations left unchanged are not detailed. Table 1 resumes the complexities related to the preemption of server operators, where var (P) denotes the set of variables in P as defined in [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF].

Algorithm 2: A Preemptable Select Iterator

Require: V = {v 1 , . . . , v k }: projection variables, I: predecessor in the pipeline Data: µ ← nil 1 Function GetNext(): SELECT operator: The projection operator π V (P) [START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF], also called SELECT, performs the projection of mappings obtained from its predecessor P according to a set of projection variables V = {v 1 , . . . , v k }. Algorithm 2 gives the implementation of this iterator. In this algorithm, Lines 4-7 are non-interruptible. This is necessary to ensure that the operator does not discard mappings without applying projection to them. Consequently, after the termination of Suspend(P), π V (P) can be suspended in O(k + |var(P)|) in space. The projection iterator reloads its local state in O(1).

2 if µ = nil then 3 µ ← I.GetNext() 4 non interruptible 5 let µ ′ ← Proj(µ, V ) 6 µ ← nil
Triple Pattern: The evaluation of a triple pattern tp over D ⟦tp⟧ D [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF] is the set of solution mappings of tp. µ is a solution mapping if µ(tp) = t where t is the triple obtained by replacing the variables in tp according to µ, such that t ∈ D. The evaluation of ⟦tp⟧ D requires to read D and produce the corresponding set of solutions mappings.

The triple pattern operator supposes that data are accessed using index scans and a clustered index [START_REF] Garcia-Molina | Database systems -the complete book[END_REF]. Algorithm 3 gives the implementation of a preemptable index scan for evaluating a triple pattern. We omitted the Stop() operation, as the iterator does not need to do any action to stop. The Save() operation stores the triple pattern tp and the index's id(t) of the last triple t read. Thus, suspending an index scan is done in constant time and the size of the operator state is in

O(|tp| + |id(t)|).
The Load() operation uses the saved index's id(t) on tp to find the last matching RDF triple read. The time complexity of this operation predominates the time complexity of Resume. This complexity depends on the type of index used. With a B+-tree [START_REF] Comer | The Ubiquitous B-Tree[END_REF], the time complexity of resuming is bound to O(log b (|D|)). B+-tree indexes are offered by many RDF data storage systems [START_REF] Erling | RDF Support in the Virtuoso DBMS[END_REF][START_REF] Neumann | The RDF-3X engine for scalable management of RDF data[END_REF][START_REF] Weiss | Hexastore: sextuple indexing for semantic web data management[END_REF]. Hash-based joins [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF][START_REF] Wilschut | Dataflow Query Execution in a Parallel Main-memory Environment[END_REF] operators are not suitable for preemption. As they build an in-memory hash table on one or more inputs to evaluate the join, they are considered as full-mappings operators. The sort-based joins and loop joins are mapping-at-a-time operators; consequently, they could be preempted with low overhead. However, for sort-based joins, we can only consider merge joins, i.e., joins inputs are already sorted on the join attribute. Otherwise, this will require to perform an in-memory sort on the inputs. In the following, we present algorithms for building preemptable Merge join and preemptable Index Loop join operators: Preemptable merge join: The Merge join algorithm merges the solutions mappings from two join inputs, i.e., others operators sorted on the join attribute. SaGe extends the classic merge join [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] to the Preemptable Merge join iterator as shown in Algorithm 4. Basically, its Stop, Save and Load functions recursively stop, save or load the joins inputs, respectively. Thus, the only internal data structures holds by the join operator are the two inputs and the last sets of solution mappings read from them. As described in Table 1, the local state of a merge join is resumable in constant time, while its space complexity depends on the size of two sets of solution mappings saved.

Preemptable Index Loop join: The Index Loop join algorithm [START_REF] Graefe | Query Evaluation Techniques for Large Databases[END_REF] exploits indexes on the inner triple pattern for efficient join processing. This algorithm has already been used for evaluating BGPs in [START_REF] Hartig | Executing SPARQL Queries over the Web of Linked Data[END_REF]. SaGe extends the classic Index Loop joins to a Preemptable Index join Iterator (PIJ-Iterator) presented in Algorithm 5. To produce solutions, the iterator executes the same steps repeatedly until all solutions are produced: (1) It pulls solutions mappings µ c from its predecessor. ( 2 A PIJ-Iterator supports preemption through the Stop, Save and Load functions. The non-interruptible section of GetNext() only concerns a scan in the dataset. Therefore, in the worse case, the iterator has to wait for one index scan to complete before being interruptible. As with the merge join, the Save and Load functions needs to stop and resume the left join input. The latter also needs to resume an Index Scan, which can be resumed in O(log b (|D |). Regarding the saved state, the iterator saves the triple pattern joined with the last set of solution mappings pulled from the predecessor and an index scan. For instance, in Figure 4b, the saved state of the join of tp 2 and tp 1 is µ c = {?v1 → wm:Product12, ?v3 → "4356"}.

UNION fragment:

The UNION fragment is defined as the union of solution mappings from two graph patterns. We consider a multiset union semantic, as set unions require to save intermediate results to remove duplicates and thus cannot be implemented as mappingat-a-time operators. The set semantic can be restored by the smart Web client using the DISTINCT modifier on client-side. Evaluating a multi-set union is equivalent to the sequential evaluation of all graph patterns in the union. When preemption occurs, all graph patterns in the union are saved recursively. So the union has no local state on its own. Similarly, to resume an union evaluation, each graph pattern is reloaded recursively. FILTER fragment: A SPARQL FILTER is denoted F = σ R (P), where P is a graph pattern and R is a built-in filter condition. The evaluation of F yields the solutions mappings of P that verify R. Some filter conditions require collection of mappings to be evaluated, like the EXISTS filter which requires the evaluation of a graph pattern. Consequently, we limit the filter condition to pure logical expressions (=, <, ≥, ∧, etc) as defined in [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF][START_REF] Schmidt | Foundations of SPARQL query optimization[END_REF]. The preemption of a FILTER is similar to those of a projection. We only need to suspend or resume P, respectively. For the local state, we need to save the last solution mappings pulled from P and R.

Table 1 summarizes the complexities of Suspend and Resume in time and space scans can be costly. Overall, the complexity of Web preemption is higher than the initial O(|Q |) stated in Section 3.1. However, we demonstrate empirically in Section 4 that time and space complexity can be kept under a few milliseconds and kilobytes, respectively.

SaGe smart Web client

The SaGe approach requires a smart Web client for processing SPARQL queries for two reasons. First, the smart Web client must be able to continue query execution after receiving a saved plan from the server. Second, as the preemptable server only implements a fragment of SPARQL, the smart Web client has to implement the missing operators to support full SPARQL queries. It includes SERVICE, ORDER BY, GROUP BY, DISTINCT, MINUS, FILTER EXIST and aggregations (COUNT, AVG, SUM, MIN, MAX), but also ▷◁, ∪, ▷◁ and π to be able to recombine results obtained from the SaGe server. Consequently, the SaGe smart client is a SPARQL query engine that accesses RDF datasets through the SaGe server. Given a SPARQL query, the SaGe client parses it into a logical query execution plan, optimizes it and then builds its own physical query execution. The leafs of the plan must correspond to subqueries evaluable by a SaGe server. Figure 5b shows the execution plan build by the SaGe client for executing query Q 3 , from Figure 5a. Compared to a SPARQL endpoint, processing SPARQL queries with the SaGe smart client has an overhead in terms of the number of request sent to the server and transferred data 9 . With a SPARQL endpoint, a web client executes a query by sending a single web request and receives only query results. The smart client overhead for executing the same query is the additional number of request and data transfered to obtain the same results. Consequently, the client overhead has two components:

Number of requests: To execute a SPARQL query, a SaGe client needs n ≥ 1 requests. We can distinguish two cases: [START_REF] Aluç | Diversified Stress Testing of RDF Data Management Systems[END_REF] The query is fully supported by the SaGe server, so n is equal to the number of time quantum required to process the query. Notice that the 9 The client overhead should not be confused with the server overhead. client needs to pay the network latency twice per request. (2) The query is not fully supported by the SaGe server. Then, the client decomposes the query into a set of subqueries supported by the server, evaluate each subquery as in the first case, and recombine intermediate results to produce query results.

Data transfer: We also distinguish two cases: (1) If the query is fully supported by the SaGe server, the only overhead is the size of the saved plan S i multiplied by the number of requests. Notice that the saved plan S i can be returned by reference or by value, i.e., saved server-side or client-side. (2) If the query is not fully supported by the SaGe server, then the client decomposes the query and recombine results of subqueries. Among these results, some are intermediate results and part of the client overhead.

Consequently, the challenge for the smart client is to minimize the overhead in terms of the number of requests and transferred data. The data transfer could be reduced by saving the plans server-side rather than returning it to clients 10 . However, the main source of client overhead comes from the decomposition made to support full SPARQL queries, as these queries increase the number of requests sent to the server. Some decompositions are more costly than others. To illustrate, consider the evaluation of (P 1 OPTIONAL P 2 ) where P 1 and P 2 are expressions supported by the SaGe server. A possible approach is to evaluate ⟦P 1 ⟧ D and ⟦P 2 ⟧ D on the server, and then perform the left outer join on the client. This strategy generates only two subqueries but materializes ⟦P 2 ⟧ D on client. If there is no join results, ⟦P 2 ⟧ D are just useless intermediate results.

Another approach is to rely on a nested loop join approach: evaluates ⟦P 1 ⟧ D and for each

µ 1 ∈ ⟦P 1 ⟧ D , if µ 2 ∈ ⟦µ 1 (P2)⟧ D then {µ 1 ∪ µ 2 } are solutions to P 1 ▷◁ P 2 .
Otherwise, only µ 1 is a solution to the left-join. This approach sends at least as many subqueries to the server than there is solutions to ⟦P 1 ⟧ D .

To reduce the communication, the SaGe client implements Bind-LeftJoins to process local join in a block fashion, by sending unions of BGPs to the server. This technique is already used in federated SPARQL query processing [START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF] with bound joins and in BrTPF [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF]. Consequently, the number of request to the SaGe server is reduced by a factor equivalent to the size of a block of mappings. However, the number of requests sent still depends on the cardinality of P 1 .

Consequently, we propose a new technique, called OptJoin, for optimizing the evaluation of a subclass of left-joins. The approach relies on the fact that:

⟦P 1 ▷◁ P 2 ⟧ D = ⟦P 1 ▷◁ P 2 ⟧ D ∪ (⟦P 1 ⟧ D \ ⟦π var (P 1 ) (P 1 ▷◁ P 2 )⟧ D )
So we can deduce that: ⟦P 1 ▷◁ P 2 ⟧ D ⊆ ⟦(P 1 ▷◁ P 2 ) ∪ P 1 ⟧ D . If both P 1 and P 2 are evaluable by the SaGe server, then the smart client computes the left-join as follows. First, it sends the query (P 1 ▷◁ P 2 ) ∪ P 1 to the server. Then, for each mapping µ received, it builds local materialized views for ⟦P 1 ▷◁ P 2 ⟧ D and ⟦P 1 ⟧ D . The client knows that µ ∈ ⟦P 1 ▷◁ P 2 ⟧ D if dom (µ) ⊂ var (P 1 ▷◁ P 2 ), otherwise µ ∈ ⟦P 1 ⟧ D . Finally, the client uses the views to process the left-join locally. With this technique, the client only use one subquery to evaluate the left-join and, in the worst case, it transfers ⟦P 1 ▷◁ P 2 ⟧ D as additional intermediate results.

To illustrate, consider query Q 3 from Figure 5a. Q 3 , with 88334 solutions. The cardinality of tp 1 ▷◁ tp 2 is also of 88334, as every actor has a birth place. This is the worse case for a BindLeftJoin, which will require 88334 Block size additional requests to evaluate the left join. However, with an OptJoin, the client is able to evaluate Q 3 in approximately 500 requests.

We implement both BindLeftJoin and OptJoin as physical operators to evaluate OPTIONALs, depending on the query. We also implement regular BindJoin for processing SERVICE queries.

EXPERIMENTAL STUDY

We want to empirically answer the following questions: What is the overhead of Web preemption in time and space? Does Web preemption improves the average workload completion time? Does Web preemption improves the time for first results? What are the client overheads in terms of numbers of requests and data transfer? We use Virtuoso as the baseline for comparing with SPARQL endpoints, with TPF and BrTPF as the baselines for LDF approaches.

We implemented the SaGe client in Java, using Apache Jena 11 . As an extension of Jena, SaGe is just as compliant with SPARQL 1.1. The SaGe server is implemented as a Python Web service and uses HDT [START_REF] Fernández | Binary RDF representation for publication and exchange (HDT)[END_REF] (v1.3.2) for storing data. Notice that the current implementation of HDT cannot ensure loд b (n) access time for all triple patterns, like (?s p ?o). This impacts negatively the performance of SaGe when resuming some queries. The code and the experimental setup are available on the companion website 12 .

Experimental setup

Dataset and Queries: We use the Waterloo SPARQL Diversity Benchmark (WatDiv 13 ) [START_REF] Aluç | Diversified Stress Testing of RDF Data Management Systems[END_REF]. We re-use the RDF dataset and the SPARQL queries from the BrTPF [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF] experimental study 14 . The dataset contains 10 7 triples and queries are arranged in 50 workloads of 193 queries each. They are SPARQL conjunctive queries with STAR, PATH and SNOWFLAKE shapes. They vary in complexity, up to 10 joins per query with very high and very low selectivity. 20% of queries require more than ≈ 30s to be executed using the virtuoso server. All workloads follow nearly the same distribution of query execution times as presented in Figure 6. The execution times are measured for one workload of 193 queries with SaGe and an infinite time quantum.

Approaches: We compare the following approaches: • SaGe: We run the SaGe query engine with various time quantum: 75ms and 1s, denoted SaGe-75ms and SaGe-1s respectively. HDT indexes are loaded in memory while HDT data is stored on disk.

• Virtuoso: We run the Virtuoso SPARQL endpoint [START_REF] Erling | RDF Support in the Virtuoso DBMS[END_REF] (v7.2.4), without any quotas or limitations .

• TPF: We run the standard TPF client (v2.0.5) and TPF server (v2.2.3) with HDT files as backend (same settings as SaGe).

• BrTPF: We run the BrTPF client and server used in [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF], with HDT files as backend (same settings as SaGe). BrTPF is currently the LDF approach with the lowest data transfer [START_REF] Hartig | Bindings-Restricted Triple Pattern Fragments[END_REF].

Servers configurations:

We run all the servers on a machine with Intel(R) Xeon(R) CPU E7-8870@2.10GHz and 1.5TB RAM.

Clients configurations: In order to generate load over servers, we rely on 50 clients, each one executing a different workload of queries. All clients start executing their workload simultaneously. The clients access servers through HTTP proxies to ensure that client-server latency is kept around 50ms.

Evaluation Metrics: Presented results correspond to the average obtained of three successive execution of the queries workloads. (1) Workload completion time (WCT): is the total time taken by a client to evaluate a set of SPARQL queries, measured as the time between the first query starting and the last query completing.

(2) Time for first results (TFR) for a query: is the time between the query starting and the production of the first query's results.

(3) Time preemption overhead: is the total time taken by the server's Suspend and Resume operations. (4) Number of HTTP requests and data transfer: is the total number of HTTP requests sent by a client to a server and the number of transferred data when executing a SPARQL query.

Experimental results

We first ensure that the SaGe approach yield complete results. We run both Virtuoso and SaGe and verify that, for each query, SaGe delivers complete results using Virtuoso results as ground truth. for suspending a running query and the time spent for resuming the next waiting query. To measure the overhead, we run one workload of queries using SaGe-75ms and measure time elapsed for the Suspend and Resume operations. Figure 7 shows the overhead in time for SaGe Suspend and Resume operations using different sizes of the WatDiv dataset. Generally, the size of the dataset does not impact the overhead, which is around 1ms for Suspend and 1.5ms for Resume. As expected, the overhead of the Resume operation is greater than the one of the Suspend operation, due to the cost of resuming the Index scans in the plan. With a quantum of 75ms, the overhead is ≈ 3% of the quantum, which is negligible.

What is the overhead in time of

What is the overhead in space of Web preemption? The overhead in space of the Web preemption is the size of saved plans produced by the Suspend operation. According to Section 3.3, we determined that the SaGe physical query plans can be saved in O(|Q |). To measure the overhead, we run a workload of queries using SaGe-75ms and measure the size of saved plans. Saved plans are compressed using Google Protocol Buffers 15 . Table 2 shows the overhead in space for SaGe. As we can see the size of a saved plan remains very small, with no more than 6 kb for a query with ten joins. Hence, this space is indeed proportional to the size of the plan suspended.

Does Web preemption improve the average workload completion time?

To enable Web preemption, the SaGe server has a restricted choice of physical query operators, thus physical query execution plans generated by the SaGe server should be less performant than those generated by Virtuoso. This tradeoff only make sense if the Web preemption compensates the loss in performance. Compensation is possible only if the workload alternates long-running and short running queries. In the setup, each client runs a different workload of 193 queries that vary from 30s to 0.22s, following an exponential distribution. All clients execute their workload concurrently and start simultaneously. We experiment up to 50 concurrent clients by step of 5 clients. As there is only one worker on the Web server, and queries execution time vary, this setup is the worst case for Virtuoso.

Figure 8 shows the average workload completion time obtained for all approaches, with a logarithmic scale. As expected, Virtuoso is significantly impacted by the convoy effect and delivers the worse WTC after 20 concurrent clients. TPF and BrTPF avoid the convoy and behave similarly. BrTPF is more performant thanks to its bindjoin technique that group requests to the server. SaGe-75ms and SaGe-1s avoid the convoy effect and delivers better WTC than TPF and BrTPF. As expected, increasing the time quantum also increases the probability of convoy effect and, globally, SaGe-75ms offers the best WTC. We rerun the same experiment with 4 workers for SaGe-75ms and Virtuoso. Figure 9 shows the average workload completion time obtained for both approaches. As we can see, both approaches benefit of the four workers. However, Virtuoso still suffers from the convoy effect. Does Web preemption improve the time for the first results? The Time for first results (TFR) for a query is the time between the query starting and the production of the first query's results. Web preemption should provides better time for first results. Avoiding convoy effect allows to start queries earlier and then get results earlier. We rerun the same setup as in the previous section and measure the time for first results (TFR). Figure 10 shows the results with a linear scale. As expected, Virtuoso suffers from the convoy effect that degrades significantly the TFR when the concurrency The TFR for SaGe-75ms and SaGe-1s increases with the number of clients and the slope seems proportional to the quantum. This is normal because the waiting time on the server increases with the number of clients, as seen previously. Reducing the quantum improves the TFR, but increases the number of requests and thus deteriorates the WTC.

What are the client overheads in terms of number of requests and data transfer? The client overhead in requests is the number of requests that the smart client sent to the server to get complete results minus one, as Virtuoso executes all queries in one request. As WatDiv queries are pure conjunctive queries and supported by the SaGe server, the number of requests to the server is the number of time quantum required to evaluate the whole workload. We measure the number of requests sent to servers with one workload for all approaches, with results shown in Table 3(a). As expected, Virtuoso just send 193 requests to the server. SaGe-75ms send 4082 requests to the server, while TPF send 2.55 × 10 5 requests to the TPF server. We can see also that increasing the time quantum significantly reduces the number of requests; SaGe-1s send only 645 requests. However, this seriously deteriorates the average WCT and TFR as presented before. To compute the overhead in data transfer of SaGe, we just need to multiply the number of requests by the average size of saved plans; for SaGe-75ms, the client overhead in data transfer is 4082 × 1, 3 kb = 5.45 Mo. As the total size of results is 51Mo, the client overhead in data transfer is ≈ 10%. For TPF, the average size of a page is 7ko; 2.5 • 10 5 × 7k = 1.78 Go, so the data transfer overhead is ≈ 340% for TPF.

What are the client overheads in terms of numbers of requests and data transfer for more complex queries? The WatDiv benchmark does not generate queries with OPTIONAL or FILTER operators. If some filters are supported by the SaGe server, the OPTIONAL operator and other filters clearly impact the number of requests sent to the SaGe server, as explained in Section 3.4. First, we run an experiment to measure the number of requests for queries with OPTIONAL. We generate new WatDiv queries from one set of 193 queries, using the following protocol. For each query Q = {tp 1 , . . . , tp n }, we select tp k ∈ Q with the highest cardinality, then we generate Q ′ = tp k ▷◁ (Q \ tp k ). Such queries verify conditions for using BindLeftJoin and OptJoin. They are challenging for the BindLeft-Join as they generate many mappings; they are also challenging for the OptJoin as all joins yield results. Table 3(b) shows the results when evaluating OPTIONAL queries with OptJoin and BindLeft-Join approaches. We observe that, in general, OptJoin outperforms BindLeftJoin. Furthermore, OptJoin is improved when using a higher quantum, as the single subquery sent is evaluated more quickly. This is not the case for BindLeftJoin, as the number of requests still depends on the number of intermediate results.

Finally, we re-use 166 SELECT queries from Feasible [START_REF] Saleem | FEASIBLE: A Feature-Based SPARQL Benchmark Generation Framework[END_REF] with the DBpedia 3.5.1 dataset, which were generated from real-users queries. We excluded queries that time-out, identified in [START_REF] Saleem | FEASIBLE: A Feature-Based SPARQL Benchmark Generation Framework[END_REF], and measure the number of requests sent to the server. Table 3(a) shows the results. Of course, Virtuoso just send 166 requests to the server. As we can see the ratio of requests between SaGe-75 and TPF is nearly the same as the previous experiment. However, the difference between SaGe-1s and SaGe-75ms has clearly decreased, because most requests sent are produced by the decomposition of OPTIONAL and FILTER and not by the evaluation of BGPs.

CONCLUSION AND FUTURE WORKS

In this paper, we demonstrated how Web preemption allows not only to suspend SPARQL queries, but also to resume them. This opens the possibility to efficiently execute long-running queries with complete results. The scientific challenge was to keep the Web preemption overhead as low as possible; we demonstrated that the overhead of large a fragment of SPARQL can be kept under 2ms.

Compared to SPARQL endpoint approaches without quotas, SaGe avoids the convoy effect and is a winning bet as soon as the queries of the workload vary in execution time. Compared to LDF approaches, SaGe offers a more expressive server interface with joins, union and filter evaluated server side. Consequently, this considerably reduces data transfer and the communication cost, improving the execution time of SPARQL queries.

SaGe opens several perspectives. First, for the sake of simplicity, we made the hypothesis of read-only datasets in this paper. If we allow concurrent updates, then a query can be suspended with a version of a RDF dataset and resumed with another version. The main challenge is then to determine which consistency criteria can be ensured by the preemptive Web server. As SaGe only accesses the RDF dataset when scanning triple patterns, it could be possible to compensate concurrent updates and deliver, at least, eventual consistency for query results. Second, we aim to explore how the interface of the server can be extended to support named graphs and how the optimizer of the smart client can be tuned to produce better query decompositions, especially in the case of federated SPARQL query processing. Third, we plan to explore if more elaborated scheduling policies could increase performance. Finally, the Web preemption model is not restricted to SPARQL. An interesting perspective is to design a similar approach for SQL or GraphQL.

Figure 1 :

 1 Figure 1: SPARQL Query Q 1 : finds all actors' birth cities.

Figure 3 :

 3 Figure 3: Possible states of a query execution in a preemptive Web Server.

  One page returned by the SaGe server during Q 2 evaluation.

Figure 4 :

 4 Figure 4: A tree representation of a page returned by the SaGe server when executing SPARQL query Q 2 with the saved plan passed by value.

Algorithm 1 : 2 let root←first iterator in I 3 Call 6 let root←first iterator in I 7 Call

 12367 Implementation of the Suspend and Resume functions following the iterator model Require: I: pipeline of iterators, S: serialized pipeline state (as generated by Suspend) 1 Function Suspend(I): root.Stop() 4 return root.Save() 5 Function Resume(I, S): root.Load(S) 8 return I Communication between operators. Bounding the time complexity of Suspend(P Q i ) to O(|Q i |) requires to avoid materialization of intermediate results when physical operators communicate.

10 Function 11 µ

 1011 Load(µ ′ ): ← µ ′

Algorithm 3 : 3 t 5 return µ 6 Function

 3356 A Preemptable Index Scan Iterator, evaluating a triple pattern tp using an index Require: tp: triple pattern, D: RDF dataset queried, I tp : clustered index over tp Data: t: last matching RDF triple read 1 Function GetNext(): ← next RDF triple matching tp in D 4 let µ ← set of solutions mappings such as µ(t) = tp Save(): 7 return ⟨tp, id(t)⟩ 8 Function Load(id): 9 t ← I tp .Locate(id) // Locate the last triple read Basic Graph patterns (AND):. A Basic Graph pattern (BGP) evaluation corresponds to the natural join of a set of triple patterns. Join operators fall into three categories [11]: (1) Hash-based joins e.g., Symmetric Hash join or XJoin, (2) Sort-based joins, e.g., (Sort) Merge join, (3) Loop joins, e.g., index loop or nested loop joins.

Algorithm 4 : 2 I 3 I 7 return 8 Function: 9 I 10 I 11 µ l ← µ ′ l 12 µ r ← µ ′ r Algorithm 5 : 2 I 3 µ c ← nil 4 I 5 Function GetNext(): 6 while 8 if µ c = nil then 9 return nil 10 I 13 return µ ∪ µ c 14 Function 15 tp r ← tp ′ 16 if µ ′ nil then 17 µ c ← µ ′ 18 I 19 I 21 let t ← the last triple read by I find 22 return ⟨tp r , µ c , t⟩ 23 Function Stop(): 24 I 25 I

 4237891011125234568910131415161718192122232425 A Preemptable Merge Join Iterator I , joining the output of two iterators I left and I right . Require: I left : the outer join input, I right : the inner join input, µ l : the last element read from I left , µ r : the last element read from I right , D: RDF dataset queried 1 Function Stop(): left .Stop() right .Stop() 4 Function Save(): 5 let s l ← I left .Save() 6 let s r ← I right .Save() ⟨s l , s r , µ l , µ r ⟩ Load(s l , s r , µ ′ l , µ ′ r )left .Load(s l ) right .Load(s r ) A Preemptable Index Join Iterator I i : a preemptable join operator used by SaGe for BGP evaluation Require: I left : the iterator responsible for the evaluation of the outer join input, tp r : the inner join input, D: RDF dataset queried. 1 Function Open(): left .Open() find ← a PreemptableIndexScanIterator over ∅ ¬I find .HasN ext() do 7 µ c ← I left .GetN ext() find ← PreemptableIndexScanIterator over ⟦µ c (tp r )⟧ D 11 non interruptible 12 let µ ← I find .GetN ext() Load(tp ′ , µ ′ , t): find ← PreemptableIndexScanIterator over ⟦µ c (tp i )⟧ D find .Load(t); 20 Function Save(): left .Stop() find .Stop()

  ) It applies µ c to tp i to generate a bound pattern b = µ c (tp i ). (3) If b has no solution mappings in D, it tries to read again from its predecessor (jump back to Step 1). (4) Otherwise, it reads triple matching b in D, produces the associated set of solution mappings and then goes back to Step 1.

  . The space complexity to Save a physical plan is established to O(|Q | × log 2 (|D|). We supposed that |var (P)| and the number of |tp| to save are close to |Q |. However, the size of index IDs are integers that can be as big as the number of RDF triples in D. Hence, they can be encoded in at most log 2 (|D |) bits. The time complexity to Resume a physical plan is O(|Q | × log b (|D |)). It is higher than the time complexity of Suspend, as resuming index PREFIX r d f s : < h t t p : / / www. w3 . o r g / 2 0 0 0 / 0 1 / r d f -schema # > PREFIX dbo : < h t t p : / / d b p e d i a . o r g / o n t o l o g y / > SELECT ? name ? p l a c e WHERE { ? a c t o r a dbo : A c t o r . # t p 1 ? a c t o r r d f s : l a b e l ? name . # t p 2 OPTIONAL { ? a c t o r dbo : b i r t h P l a c e ? p l a c e . # t p 3 } } (a) SPARQL query Q 3 : finds all actors with their names and their birth places, if they exist.

  Client-side physical query execution plan.

Figure 5 :

 5 Figure 5: Physical query execution plan used by the SaGe smart Web client for the query Q 3 .

Figure 6 :

 6 Figure 6: Distribution of query execution time.

Figure 8 :

 8 Figure 8: Average workload completion time per client, with up to 50 concurrent clients (logarithmic scale).

Figure 9 :

 9 Figure 9: Average workload completion time per client, with 4 workers (logarithmic scale).

Figure 10 :

 10 Figure 10: Average time for first results (over all queries), with up to 50 concurrent clients (linear scale).

Table 1 :

 1 Complexities of preemption of physical query iterators. |id | and |tp| denote the size of encoding an index key and a triple pattern, respectively.

	Preemptable	Space complexity	Time complexity of Remarks
	iterator	of local state	loading local state
	π v1,...,vk (P)	O(k + |var (P)|)	O(1)
	Index Scan tp	O(|tp| + |id |)	O(log b (|D|))	Require indexes
				on all kinds of
				triple patterns
	Merge Join	O(|var (P 1 )| + |var(P 2 )|)	O(1)
	P 1 ▷◁ P 2
	Index Loop	O(|var (P)| + |tp| + |id |)	O(log b (|D|))
	Join P ▷◁ tp
	P 1 UNION P 2	O(1)	O(1)	Multi-set Union
	P Filter R	O(|var (P)| + |R|)	O(1)	Pure logical ex-
				pression only
	Server physi-	O(|Q | × log 2 (|D|)	O(|Q | × log b (|D|))
	cal plan

Table 2 :

 2 Space of saved physical query execution plans.

	11 https://jena.apache.org/
	12 https://github.com/sage-org/sage-experiments
	13 http://dsg.uwaterloo.ca/watdiv/
	14 http://olafhartig.de/brTPF-ODBASE2016

Table 3 :

 3 Average number of HTTP requests sent to server increases. TPF and BrTPF do not suffer from the convoy effect and TFR is clearly stable over concurrency. The main reason is that delivering a page of result for a single triple pattern takes ≈ 5ms in our experiment, so the waiting time on the TPF server grows very slowly. BrTPF is better than TPF due to its bind-join technique.

https://www.w3.org/TR/2013/REC-sparql11-protocol-20130321/

All results were obtained on DBpedia version 2016-04.

S i can be returned to the client or saved server-side and returned by reference.

Preemption and concurrent updates raise issues on correctness of results.

This is a clear reference to full-relation and tuple-at-a-time operators in database systems[11][Chapter 15.2]

In our implementation, we choose to save plans client-side to tolerate server failures.

ACKNOWLEDGMENTS

This work has been partially funded through the FaBuLA project, part of the AtlanSTIC 2020 program.


Julie Delclaux

Biodiversity conservation in agricultural landscapes: statistical analysis method to understand media representation of policies and species

Correspondant analysis on covariate "year" Similarity analysis with co-occurence index on sentence segments Politicals events are the major factors of the media coverage Articles move from an ecocentrist viewpoint to an anthropocentrist viewpoint The media contribute to public opinion and have an agenda-setting function (McCombs and Shaw, 1972) Understanding the media representation of policies and species could improve biodiversity conservation strategies (Jacobson and al., 2012) We sought to analyze topical content on newspaper coverage and the effect of time with a reproducible statistical method nationa l natura l

.0 0.1 0.2 0.3 -0.3 -0.2 -0.1 0.0 0.1 0.2 X.date_2017 X.date_2016 X.date_2014 X.date_2015 X.date_2013 X.date_2012 X.date_2011 X.date_2009 X.date_2010 X.date_2007 X.date_2008 X.date_2006 X.date_2005 X.date_2004 X.date_2002 X.date_2001 X.date_2003 X.date_1999 X.date_2000

  mellifera), wolf (Canis lupus) and bear (Ursus arctos) are the most mentioned species Bee is associated with ecosystem services while wolf and bear are threatened but also the place of dif�icult trade-offs between conservation and production objectives

  discusses more of human dimensions than national park Time Effect on Topical Content Species have oposite valences and some biodiversity policies are mentionned in synergy with agriculture Topic content changes over time under political impulses and the viewpoint of articles becomes anthropocentrist Textual analysis allows to analyze �inely the content, the valence and the time trends but not the sources of the articles (scienti�ic papers, interviews...) d ra g o n �l y


Jiajun Pan
email: jiajun.pan@ls2n.fr

Hoel Le Capitaine
email: hoel.lecapitaine@ls2n.fr

Philippe Leray
email: philippe.leray@ls2n.fr

Relational Constraints for Metric Learning on Relational Data

Most of metric learning approaches are dedicated to be applied on data described by feature vectors, with some notable exceptions such as times series, trees or graphs. The objective of this paper is to propose a metric learning algorithm that specifically considers relational data. The proposed approach can take benefit from both the topological structure of the data and supervised labels. For selecting relative constraints representing the relational information, we introduce a link-strength function that measures the strength of relationship links between entities by the side-information of their common parents. We show the performance of the proposed method with two different classical metric learning algorithms, which are ITML (Information Theoretic Metric Learning) and LSML (Least Squares Metric Learning), and test on several real-world datasets. Experimental results show that using relational information improves the quality of the learned metric.

Introduction

Sample similarity measurement lies at the heart of many classification and clustering methods in pattern recognition and machine learning. For instance, in classification, the k-Nearest Neighbor classifier uses a metric to identify the nearest neighbors; in clustering algorithms, k-means rely on distance measurements between data points; in information retrieval, documents are often ranked according to their relevance to a given query based on similarity scores. The performance of these algorithms rely on the quality of the metric. The conventionally used Euclidean distance cannot give a convenient dissimilarity in many cases, due to the distribution of the data (see (Tenenbaum, De Silva, and Langford 2000)). Thus, it calls a great need for appropriate ways to measure the distance or similarity between observations in learning algorithms.

Metric learning has now been used for more than a decade to deal with this problem, and can be seen a feature/representation learning allowing the use of Euclidean distances later on. The vast majority of metric learning approaches are dedicated to be applied on data described by feature vectors, where the objective is generally to learn a Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. matrix M that is used for the Mahalanobis distance

D 2
M (x, y) = (x -y) T M (x -y), where x and y are d-dimensional vectors and M is a positive semi-definite matrix. Using such a metric is equivalent to perform a linear projection of the data by the matrix decomposition M = L T L, where L ∈ R k×d , and then use the conventional Euclidean distance in this new feature space.

The interested reader can refer to reviews in [START_REF] Kulis | [END_REF] and (Bellet, Habrard, and Sebban 2015).

In this model, M contains the learned parameters and is learned mostly from supervised information. Most of the approaches make use of label constraints, which means that the constraints are generated by the target labels or other supervised information. Such a distance is perfectly adapted for flat or iid data, but obviously fails to take into account complex and/or (semi-)structured, non-iid data without considering the structured information.

There are some notable exceptions such as times series in [START_REF] Garreau | Metric learning for temporal sequence alignment[END_REF]) (through dynamic time warping methods) and trees or graphs in [START_REF] Bellet | Learning discriminative tree edit similarities for linear classification application to melody recognition[END_REF]) (by using an edit distance) or networks, proposed in (Shaw, Huang, and Jebara 2011). Relational databases are increasingly used in almost all applications. A lot of real world datasets present aspects of multi-relation between the observations. For instance, social service networks, Wikipedia network, molecular biology classification and so forth. These databases are organized based on a relational model of data which contains entity tables and association tables between entity tables. Using this data in machine learning is now under consideration for years (Getoor 2007), but to the best of our knowledge, no attention on metric learning has been paid for such data. Naturally, one can use traditional metric learning algorithms for individual entities, but at the price of losing rich information coming from the relational structure of the data. Taking good use of associations between entities can help to improve metric performance.

The goal of this paper is to propose the use of both relational information and supervised information in constraints selection for metric learning. Such a definition allows to build rich models, which can eventually be used for domain adaptation, transfer learning, feature learning and data visualization with both flat and multi-relational data. In particular, we propose a solution that is able to incorporate rela-tional information within metric learning, and then illustrate its benefit compared to traditional flat approaches.

Note that the proposed approach starts from (hyper)graph data, where as approaches as in (Dhillon, Talukdar, and Crammer 2012). Instead of using label constraints, the authors used graph based constraints which enforces the distance between the unlinked node and target node to be bigger than the distance between the k-farthest linked node and target node. We propose a more general model denoted as linkstrength constraints which is generated by a link-strength function measuring the similarity of nodes by the side information of the relationships between them. The proposed link-strength function gives the possibility of using similarity learning to encode the relational information into the constraints for metric learning algorithm.

This paper is organized as follows. We recall basic definitions related to metric learning, as well as related works, in section . In section , we present our approach, which is validated by experimental comparisons on real-world datasets in section . Final comments and perspectives are drawn in section .

Related Works Metric Learning and Relational Learning

Since its seminal paper in 2003 [START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF], there have been many propositions dealing with learning metrics. In [START_REF] Kulis | [END_REF], one can find a number of different metric learning algorithms. Most of the propositions of metric learning rely on a new metric D (x, y) as D(f (x), f (y)) with a mapping function f . The metric learning then simply consists in learning the projection f by using constraints on the (dis)similarity on observations. With constraints generated from given information, metric learning approaches generally consider the generic loss function written as

L(M ) = (i,j,k)∈C M (i, j, k) + λr(M ),
where M (i, j, k) is the encoded loss from pairs of entity nodes (i,j) in set S = {(i, j)} of similar observations and pairs of entity nodes (i,k) in set D = {(i, k)} of the dissimilar observations. r(M ) is a regularization term on the matrix M (e.g Frobenius norm, trace-norm). The loss C M (i, j, k) is then generally written as the hinge loss functions max(0, D M (x i , x j )-u) and max(0, l -D M (x i , x k )) with threshold parameters u and l or max(0, m

+ D M (x i , x j ) - D M (x i , x k )) with margin parameter m.
Traditionally, in metric learning, one uses label constraints in order to select similar and dissimilar constraint sets by the target label or other supervised information. In this case, the pair (i, j) contains the nodes in same class, while the labels of nodes (i, k) are different.

Relational learning deals with learning models for which data consists in a generally complex relational structure. As a difference with flat datasets, the main learning tasks pay more attention on supervised information from the relations and knowledge from the topology of the relational graph. Collective classification is classification of related entities that may share identical classes [START_REF] Sen | Collective classification in network data[END_REF]) from the relationship information.

Note that, in [START_REF] Dumančić | Demystifying relational latent representations[END_REF], the authors propose an analysis of the meaning of the latent space learned by a deep learning algorithm on relational datasets, mainly because of the black box problem of deep approaches. The same analysis can be conducted for the meaning of metric learning, which can also be treated as mapping original feature space to a latent space. This paper mainly focuses on the usefulness of latent space and the redundancy of the latent features. They show the good performance of using unsupervised relational information for a classifier in a latent space. We specifically focus on using relational information for collective classification.

For collective classification, there are several approaches to learn metric with relational information. In (Kramer, Lavrač, and Flach 2001), they use graph relational information with propositionalization, transfer the relational representation of a learning problem into a propositional representation. Another approach uses metric learning on graphs for domain adaptation (Dhillon, Talukdar, and Crammer 2012). To this aim, they propose an iterative learning algorithm on the graph. From the resource domain, the nodes with labels, they learn a new metric and apply it on related target domain, the nodes without labels. Then, the graph is updated depending on the learned distance, and constraints with low entropy instances are selected for next iteration.

Those approaches do not consider the different modalities of the observations (features and relations). In many cases, the structure of the data does not allow to directly measure distances as if the observations were belonging to an Euclidean space. In particular, complex and structured data needs to be processed in a different way than usual tabular data. Such complex data includes times series, videos, graphs, relational data, without exhaustivity. Some metric learning algorithms consider relational data as heterogeneous networks for each different relationships. For instance, in (Zhai, Peng, and Xiao 2013), they propose a heterogeneous metric learning algorithm, which integrates the structure of different graphs into a joint graph regularization. They use two mapping function for the feature space of the object entities and subject entities in one relation, and then introduce a joint graph regularization for iterative optimize the loss function. In (Dong, Chawla, and Swami 2017), they start from the same principle but use meta-pathbased random walks to incorporate the heterogeneous network structures into skip-gram vectors for dealing with the relational graph. Those algorithms use joint regularization for different entities in heterogeneous networks, with good performance on considering the structure information in relational dataset. However, without considering the side information in the relational links. It processes the relational variables the same way as the entities and subject to their algorithm, but it ignores the differences between entity tables and association tables. Our proposed method includes the value of different variables on the relationship in the datasets and distinguish them with entities.

In this paper, we consider the case of relational data, where several tabular datasets (entities) are linked together through associations. The basic principle of our approach is to use relational links between entities when setting the constraints of the metric learning algorithm. Consequently, this approach can be used in any constraint-selection based metric learning algorithm.

Metric Learning with Relational Constraints

Recently, some metric learning approaches have been focusing on graph data. In this context, the structural information consists in the presence or absence of links between nodes of the graph. Constructing the set of similar nodes and dissimilar nodes then just uses the adjacency matrix of the graph. For example, the simplest relative link constraints is

D M (x i , x j ) ≤ D M (x i , x k )+m, (i, j) ∈ S, (i, k) ∈ D with the adjacent matrix A ij = 1, A ik = 0, ∀(i, j) ∈ S, ∀(i, k) ∈ D,
which only check the relative distance between the connected and disconnected relational links. In the sequel, this method is termed as relative link constraint.

In (Shaw, Huang, and Jebara 2011), they formulate the metric in a preserving embedding structure and learn from linear constraints with the graph topology. They proposed nearest neighbor graphs and maximum weight subgraphs, which are two ways for generating the supervised constraints with the relational information in graphs. The nearest neighbour constraints is denoted as

D 2 M (x i , x j ) > (1 - A ij ) max l (A il D 2 M (x i , x l ))
, ∀i, j which aims to constraint the disconnected node to be more far from the target node than its farthest connected node (neighbour).

However, this approach does not take into account that there are a lot of information in the valued link with numerical or categorical variables. Furthermore, target labels of nodes are not used in this model. We propose to define new relative link constraints from to the link-strength constraints, with a link-strength function to measure the importance of the relational links between entities, as well as using the supervised information obtained from the labels.

On selecting constraints with link-strength function

In this paper, our objective is to propose a new approach of metric learning considering enforcing constraints with both the relational links and label information. The basic statement behind our proposal is that we consider that two connected individuals are more similar than two unconnected individuals. We then evaluate the amount of link similarity between individuals by considering their common parents in the graph. If, furthermore, labels are available for individuals, this can be incorporated into the learning algorithm. Consequently, our approach can be both supervised or unsupervised, depending on the availability of the information in the data. We extend the relative link constraints by separating S and D with a dedicated link-strength function. The proposed constraints enhance the classical metric learning algorithms using relative constraints, such as ITML [START_REF] Davis | Information-theoretic metric learning[END_REF] and LSML [START_REF] Liu | Metric learning from relative comparisons by minimizing squared residual[END_REF].

A link-strength function LS(x i , x j |r) is a function with the input is the relational information between the entities nodes x i and x j and the output is a real value to measure the "strength" or the similarity of the two nodes. The symbol r represents the relationship information of the entities nodes x ∈ R n×d , where n is the number of instances and d the number of node attributes.

There are many ways to encode the relational information for this link-strength function, and we choose sideinformation of the common parents between the input nodes.

A relational schema R = R e ∪ R r contains a set of relational information where R e denotes the set of groups and types between entities in same tables and R r denotes the set of reference links between different tables. For a relation subset r k ⊆ R r including all references between two entity tables, for example like the reference Ratings between User and Movie as shown in Figure 1, we consider it as a manyto-many relationship. Let P ij be the set of common parents of x i and x j , and ij = |P ij |, the number of common parents.

In Figure 2, we give a subsample of a bipartite relational graph, along with an example of common parents.

Naturally, the similar node would get the similar references from the same parents node. Consequently, we consider that the link-strength depends on the side-information of the common parents which are the values of the references.

Additionally, the references can be quantified by α numerical variables v and β categorical variables v * , see Figure 3.

Given a relation r k , we propose to defined the linkstrength function as:

LS(x i , x j |r k ) = LS(x i , x j |P ij ) = ij h=1 (γ • w(h, i, j) + (1 -γ) • z(h, i, j)) (1)
where

w(h, i, j) = α m=1 exp (-|v m (p h , x i ) -v m (p h , x j )|) , and
z(h, i, j) = β m=1 (v * m (p h , x i ) • v * m (p h , x j )) ,
in which x • y = 1 iff x = y, and 0 otherwise, and p h is the h-th parent node in the set P ij . Note that numerical association attributes v are normalized in the unit interval prior to link strength computation. Note also that we restrict to unitlength slot chains, i.e. the length of the sequence of foreign key references is equal to 1. Then, we select the strongest links as similarity constraints, and the weakest links as dissimilarity constraints. The corresponding algorithm is given in Algorithm 1. Remark that if two entities x i and x j do not have common parents, their link strength is zero, and therefore considered as dissimilar.

In this paper, we mainly focus testing the proposed algorithm on one R r relation dataset. However, this link-strength function could be easily extended to multi-relational datasets by summing the link-strength for each relations. It could also LS ← LS \ {S ∪ D} 11: end while 12: return {S, D} be extended from the reference relation R r to R e , that consider the group structures as every edge between nodes is the side-information of common parents but as binary value. In that case, the link-strength function would consider the additional term

x 1 1 x 1 2 x 1 3 x 1 4 x 2 1 x 2 2 x 2 3 x 2 4 Relation R 2 Relation R
k ij k v m P k (i, j),
where P k (i, j) is the parent adjacency matrix of the relation k in the group structure defined as

P k (i, j) = 1 if xi and xj have common parents in relation r k 0 otherwise, ( 2
)
and k ij is the number of common parents of x i and x j in the relation r k .

With the link-strength function, we select the relative constraints set C = {(i, j, k) : LS(x i , x j ) ≥ LS(x i , x k )} and use the constraints on two different classical metric learning algorithms, ITML and LSML.

Experiments Datasets and Tasks

We conduct experiments to compare the performance of the constraints generated by link-strength function and the constraints generated by the label information. To compare fairly, we set the amount of constraints generated by different ways are same and the formula are both in the relative distance constraint. Basically, any relational data for which classification is needed can be tackled by our proposition.

We consider several real-world relational datasets which contains feature information for mapping with the learned metric, the target label information, and the relational information (existing links or valued links). We learn the metric of one entity table for predicting target label, so for the same dataset, we can learn different metrics for different tasks.

Here are the descriptions of the chosen datasets and tasks:

Figure 3: The side information of references from common parents P ij to node x i and node x j , in the movie dataset.

• Movie: MovieLens dataset (Harper and Konstan 2016) is a classical relational dataset which is widely used in many related papers. It consists of a relational table which has 100,000 ratings (1-5) from 943 users on 1682 movies; a movie entity table with feature information about the movies; and a user entity table with id, age, gender, occupation, and other feature information on users. Each user has rated at least 20 movies so the relational supervised information is quite dense. We define two tasks on this dataset:

-Movie-item: We select the movies table as the entity table to learn the metric on. We choose the most popular genre as the target label and use the release date and other genres as the attributes. -Movie-year: We select the users table as the entity table to learn the metric on. The age of users is discretized into 5 bins as the target label and the other feature information are the attributes.

• BookCX: We also consider the book-crossing database [START_REF] Ziegler | Improving recommendation lists through topic diversification[END_REF]. We select a randomly sampled subset BookCX from the data. This subset contains 2,400 users giving 5,000 ratings (1-10) on 10,000 books. For this dataset, we use the bag-of-words model to encode the text information from the titles, the authors and the publishers into binary attributes.

-BookCX-year: We consider the public year segmented into 5 bins as the target label and the bag-of-word of text information as the attributes. -BookCX-word: We apply PCA (Principal Component Analysis) on the bag-of-word of text information and limit the number of dimensions to 12. Then we randomly choose one of the processed dimension and seg-ment it into 5 bins as the target label. The other features are considered as attributes.

• Citelike: There are two versions of citelike dataset, Citelike-t and Citelike-a, both used in the paper (Wang, Chen, and Li 2013). They were collected from CiteU-Like and Google Scholar. CiteULike allows users to create their own collections of articles. There are abstracts, titles, and tags for each article. They manually select hundreds of seed tags and collect all the articles with at least one of these tags. They also crawl the citations between the articles from Google Scholar. Note that the final number of tags associated with all the collected articles is far more than the number of seed tags. To reduce the computation complexity, we apply PCA on the large and sparse tag feature space and limit the number of dimensions to 12. We randomly choose one of the processed features and segment it into 5 bins as the target label. Note that the sampling of Citelike-t and Citelike-a are independent and the density of the links is different.

• Mondial: This dataset [START_REF] May | Information extraction and integration with FLORID: The MONDIAL case study[END_REF]

Result and Analysis

For all the used datasets, the balance parameter between association attributes in the link-strength function is set to γ = α α+β in order to adapt to different situations of the datasets, where α is the number of numerical variables and β is the number of categorical variables as mentioned before.

The evaluation of the proposition is done by comparing the effect of learned metric with k-nearest-neighbour classification. For the set of k-nn classification, we use k equal to 5 and score the performance with accuracy rate via randomly shuffled 3-fold cross validation. Note that we tried different values for k (in particular 3, 5, 7 and 9), and the results were consistent with the results reported here for k = 5 on most datasets.

For each experiment, the number of constraints varies from 100 to 500, and we give the average value of each sets as the final result. All the experiments were run on a 3.1Ghz Intel Core i5 processor, with 16 Go 1867 MHz DDR3, and the code will be published for research reproducibility. We also give results obtained without learning a metric, i.e. using an Euclidean distance for k-nn algorithm (Euc). Results are given in Tables 1 and2.

In Tables 1 and2, Lab indicates the result obtained using only the constraints generated from label, Rel shows the result obtained by the constraints generated from the relative link constraints, i.e. using the adjacency matrix A of the graph. Pro gives the performance of our proposition based on link-strength constraints and Both shows the best result with both label constraints and the link-strength constraints while the proportion of them are appropriated. The Table 3 and 4 show the results with different set of proportion of label constraints and the link-strength constraints. Proportion equal to 1 corresponds to the situation of using only labels, and a proportion of 0 corresponds to the fact of using only link-strength based constraints. As can be seen in the Table, results tend to be better when using mostly link-strength constraints.

As can be seen, except on Movie-item task and BookCXyear task, comparing with constraints generated only from labels, the link-strength constraints lead to a great improvement of accuracy. On most datasets, the link-strength constraints shows better performance than the relative link constraints, except the BookCX-word task with ITML. For both labels and relational information, it provides a better accuracy than the constraints obtained from labels and similar to the constraints generated with link-strength function. Considering the different number of references in these datasets, for example 100, 000 references for 943 entities for Movieuser and 5,000 references for 10,000 entities for BookCXyear, we speculate that density or sparsity of the references leads to the deviation of results.

Conclusion

In this paper, we propose a simple, yet effective, way of learning a metric dedicated to (multi-)relational data. This work on relational metric learning clearly shows the benefit, in terms of accuracy, of considering relational information between entities instead of the sole consideration of labels. As a first perspective, we plan to consider other way of computing link strength, that may be inspired from graph analysis techniques, e.g. connection strength metric, length of the shortest path, value of the maximum network flow between nodes. In particular, we want to consider slot chains (i.e. sequences of foreign key references) which are longer than 1. We also plan to define a dedicated relational metric that could be learned directly, instead of setting relational constraints on standard metric learning algorithms.

Figure 1 :

 1 Figure 1: Typical example of an Entity-Association relational model

  contains the relational version of the geographical Web data sources which is composed of CIA World Factbook, a predecessor of Global Statistics, additional textual sources for coordinates, the International Atlas and some geographical data of the Karlsruhe TERRA database. We chose part of the entity table City to learn and use the table Countries as the parent table. The population is segmented into 5 bins as the target label

Table 1 :

 1 ±0.46 90.35 ±0.32 71.24 ±7.77 Both 98.67 ±0.50 69.48 ±3.08 36.97 ±1.69 90.43 ±0.72 92.65 ±0.40 90.35 ±0.32 72.00 ±7.16 The accuracy score of knn with ITML ±0.46 68.28 ±4.00 36.16 ±1.25 90.36 ±0.91 88.03 ±0.45 88.94 ±0.55 68.97 ±7.99 Lab 99.06 ±0.58 65.92 ±5.38 36.36 ±1.06 94.46 ±1.06 85.53 ±0.67 94.62 ±0.33 68.45 ±8.47 Rel 98.63 ±0.52 66.67 ±4.03 36.21 ±1.21 94.91 ±0.41 85.65 ±0.63 94.62 ±0.65 70.25 ±6.47 Pro 98.63 ±0.40 66.98 ±4.63 36.42 ±1.52 94.92 ±0.61 85.69 ±0.57 94.63 ±0.42 70.62 ±7.04 Both 99.12 ±0.52 66.98 ±4.63 36.42 ±1.15 94.92 ±0.61 85.69 ±0.57 94.63 ± 0.30 71.03 ±7.35

	ITML Movie-item	Movie-user BookCX-year BookCX-word	Citelike-t	Citelike-a	Mondial
	Euc	98.58 ±0.46 68.28 ±4.00 36.16 ±1.25	90.36 ±0.91	88.03 ±0.45 88.94 ±0.55 68.97 ±7.99
	Lab	98.62 ±0.52 67.72 ±5.38 36.19 ±1.09	89.57 ±0.87	85.91 ±0.62 89.89 ±0.23 70.39 ±8.29
	Rel	97.48 ±0.66 68.66 ±3.40 36.12 ±1.17	91.29 ±0.74	90.76 ±0.56 89.94 ±0.41 71.55 ±5.54
	Pro 92.06 LSML Movie-item 97.54 ±0.42 69.04 ±4.02 36.38 ±1.62 90.33 ±0.74 Movie-user BookCX-year BookCX-word Citelike-t	Citelike-a	Mondial
	Euc	98.58

Table 2 :

 2 The accuracy score of knn with LSML ±0.52 67.72 ±5.38 36.19 ±1.09 89.57 ±0.87 85.91 ±0.62 89.89 ±0.23 70.39 ±8.29 0.8 98.52 ±0.23 66.21 ±3.71 36.21 ±1.06 89.52 ±0.55 86.71 ±0.67 89.71 ±0.42 72.00 ±7.16 0.6 98.42 ±0.54 66.87 ±4.09 36.66 ±1.67 89.41 ±0.82 92.65 ±0.40 89.61 ±0.31 71.03 ±6.22 0.4 98.67 ±0.50 67.65 ±4.82 36.97 ±1.69 88.87 ±0.78 90.87 ±0.38 89.91 ±0.35 70.82 ±7.66 0.2 97.32 ±1.52 69.48 ±3.08 36.28 ±1.16 90.43 ±0.72 91.24 ±0.41 90.21 ±0.37 69.21 ±7.98 0.0 97.54 ±0.42 69.04 ±4.02 36.38 ±1.62 90.33 ±0.74 92.06 ±0.46 90.35 ±0.32 71.24 ±7.77

	Proportion Movie-item	Movie-user BookCX-year BookCX-word	Citelike-t	Citelike-a	Mondial
	1.0	98.62

Table 3 :

 3 The accuracy score of knn with ITML while the proportion of label constraints and the link-strength constraints gradient change from full label constraints to full link-strength constraints.

	Proportion Movie-item	Movie-user BookCX-year BookCX-word	Citelike-t	Citelike-a	Mondial
	1.0	99.06 ±0.58 65.92 ±5.38 36.36 ±1.06	94.46 ±1.06	85.53 ±0.67 94.62 ±0.33 68.45 ±8.47
	0.8	99.04 ±0.54 65.67 ±4.32 36.22 ±1.14	94.89 ±0.60	85.46 ±0.61 94.59 ±0.38 71.03 ±7.35
	0.6	99.12 ±0.52 65.78 ±3.80 36.13 ±1.18	94.78 ±0.58	85.53 ±0.79 94.61 ±0.41 70.22 ±8.42
	0.4	99.08 ±0.67 66.21 ±4.52	36.3 ±1.50	94.85 ±0.68	85.45 ±0.70 94.63 ±0.30 69.79 ±6.54
	0.2	98.87 ±0.62 66.14 ±5.39 36.42 ±1.15	94.83 ±0.86	85.45 ±0.67 94.63 ±0.52 70.67 ±7.22
	0.0	98.63 ±0.40 66.98 ±4.63 36.42 ±1.52	94.92 ±0.61	85.69 ±0.57 94.63 ±0.42 70.62 ±7.04

Table 4 :

 4 The accuracy score of knn with LSML while the proportion of label constraints and the link-strength constraints gradient change from full label constraints to full link-strength constraints.