Arnaud Grall
email: arnaud.grall@univ-nantes.fr

Hala Skaf-Molli

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

Matthieu Perrin
email: matthieu.perrin@univ-nantes.fr

Collaborative SPARQL Query Processing for Decentralized Semantic Data

Keywords: Decentralized Data Management, SPARQL query processing, sources discovery

Decentralization allows users to regain freedom and control over their digital life. As a global shared data space, the Linked Data already supports decentralization. Data providers are free to publish their data on their web domains and users can execute decentralized SPARQL queries over multiple data sources. However, decentralization makes query processing challenging, raising well-known problems of source discovery, answer completeness and performance. Existing approaches for decentralized SPARQL query processing raise issues related to autonomy and answer completeness. In this paper, we propose Qasino, an original approach for querying decentralized RDF data that targets both answer completeness, and source autonomy. Qasino is based on a decentralized random service that allows for discovering all relevant data sources. To speed up query processing, sources executing similar queries cooperate by sharing their intermediate results. Our experimental results demonstrate that collaborative query processing can significantly speedup query processing in a decentralized setup.

Introduction

Decentralization is a common way to give users back control over their digital life. As a global shared data space, the Linked Data already supports decentralization. Data providers are free to publish their data on their web domains and users can execute decentralized SPARQL queries over multiple data sources. However, decentralization introduces challenging problems for query processing related to well-known problems of source discovery, completeness and performance. Discovering all relevant sources for a query remains an issue. Existing federated query engines assume the existence of a catalog [START_REF] Acosta | ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints[END_REF][START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF]. Link traversal [START_REF] Hartig | Zero-knowledge query planning for an iterator implementation of link traversal based query execution[END_REF] crawls links from a seed URI during query execution but cannot ensure that all relevant sources are reachable from the seed. Semantic P2P data management [START_REF] Crespo | Semantic overlay networks for p2p systems[END_REF] rebuild overlay networks on top of sources to allow efficient discovery. However, P2P data management raises issues on autonomy, i.e. participants must agree to participate in common tasks such as routing, indexing, and replication.

In this paper, we propose Qasino, an original approach for querying decentralized RDF data that targets both answer completeness and sources autonomy. Qasino relies on a decentralized random service ables to return a random participant. Thanks to the random service, Qasino crawls the set of participants while running a query. Crawling allows to discover both sources and similar running queries. Similar queries collaborate by sharing queries intermediate results and random draws. Collaboration allows to speed up queries termination while producing complete results. In this paper, we propose the following contributions:

-A new model for decentralized SPARQL query processing.

-A collaborative Monte-Carlo SPARQL query execution algorithm that allows collaborative discovery of datasources. If several participants execute similar queries, then they will eventually meet several times during query execution and share their results. Collaboration allows to speed up query termination and provides probabilistic guarantee on answers completeness. -A simulator to run experimentations with thousands of participants, which goes beyond traditional decentralized query experimentations.

The paper is organized as follows. Section 2 describes the related works. Section 3 presents the Qasino approach. Section 4 presents Qasino algorithms. Section 5 presents experimental results. Section 6 concludes contributions and presents future works.

Related Works

Decentralization allows users to store their RDF data where they want on the Web. However, executing a SPARQL query over decentralized data requires to discover all relevant data sources. Solving the discovery problem at the scale of the Web while preserving sources autonomy is still an open issue.

The Solid project [START_REF] Mansour | A demonstration of the solid platform for social web applications[END_REF] promotes the vision of a decentralized web for social web applications. In Solid, users store their data in personal online datastores (pods). However, Solid does not describe how to run a query over a large-scale network of pods.

Link traversal [START_REF] Hartig | Zero-knowledge query planning for an iterator implementation of link traversal based query execution[END_REF] allows to execute SPARQL queries directly on the Linked Data resources, relying on URI dereferencing. Link traversal starts the query execution from a seed URI provided by users and considers every URI appearing in mappings as a new data source. Therefore, it is up to the user to know at least one seed, and the link traversal is able to discover new sources during query processing. Therefore, sources discovery is partially in charge of data consumers, moreover, query answer completeness is defined according to the reachability semantics [START_REF] Hartig | Sparql for a web of linked data: Semantics and computability[END_REF].

Federated query engines [START_REF] Acosta | ANAPSID: An Adaptive Query Processing Engine for SPARQL Endpoints[END_REF][START_REF] Schwarte | FedX: Optimization Techniques for Federated Query Processing on Linked Data[END_REF] allow data consumers to execute queries over a catalog of data sources. It is up to the data consumers to provide this catalog. Building this catalog traditionally implies to collect the description of all potential sources, which is again in charge of data consumers. The query answer completeness is defined according to the set of sources contained in the catalog.

Many systems rely on Distributed Hash Tables (DHT) such as P-Grid [START_REF] Aberer | P-grid: a self-organizing structured p2p system[END_REF] or GridVine [START_REF] Aberer | Gridvine: Building internet-scale semantic overlay networks[END_REF] for sources discovery. However, DHT systems do not allow users to choose where their data are stored, consistent hashing determine where data should be stored. DHT can be used also just as a distributed catalog and data remain located where users want as in the InterPlanetary File System (IPFS). In this case, participants have to agree to participate to keybase routing and store informations that do not belong to them.

Recently, unstructured P2P techniques have gained attention of Semantic Web community as potential decentralized architectures for Linked Data management [START_REF] Aebeloe | A decentralized architecture for sharing and querying semantic data[END_REF][START_REF] Grall | Ladda: SPARQL queries in the fog of browsers[END_REF][START_REF] Grall | SPARQL query execution in networks of web browsers[END_REF][START_REF] Marx | A decentralized architecture for sparql query processing and rdf sharing: A position paper[END_REF][START_REF] Polleres | A more decentralized vision for linked data[END_REF]. Existing approaches maintain a neighborhood for each site. As a participant does not know where data are located, she floods the network with her query [START_REF] Aebeloe | A decentralized architecture for sharing and querying semantic data[END_REF]. However, this approach does not scale and hardly delivers complete results. Flooding can be avoided with super-peer maintaining routing indices as in [START_REF] Nejdl | Super-peer-based routing and clustering strategies for rdf-based peerto-peer networks[END_REF]. Having super-peers in a network of nodes is possible but they represent a point of failure which is a strong limitation to massive deployment of distributed applications in nodes. Flooding can also be reduced with spanning trees as in sensor networks [START_REF] Diallo | Distributed database management techniques for wireless sensor networks[END_REF]. A spanning tree reduces the flooding to the number of nodes in the network. However, spanning trees are costly to maintain on large networks with heavy churn. The network traffic can be significantly reduced using adapted replication strategies and random walks [START_REF] Lv | Search and replication in unstructured peer-to-peer networks[END_REF]. Flooding can also be limited by using multiple overlays as in Semantic Overlay Network (SON) or routing indices [START_REF] Crespo | Semantic overlay networks for p2p systems[END_REF][START_REF] Doulkeridis | Distributed semantic overlay networks[END_REF]. Participants are clustered in communities according to their common interests. Queries are routed to the right community to be executed. SON restricts the number of sources for a query. This supposes that participants agree to compute this routing and maintain information that are not directly relevant for executing their queries.

In both structured or unstructured P2P networks, solving the discovery problem requires participants to loose autonomy. Participants have to route all messages, not only those they want and they cannot choose data to host or to replicate. In Qasino, we explore an original P2P approach that requires only that participants accept to be discovered.

Qasino Approach and Models

In Qasino, we consider a community of participants. We aim to preserve two properties: (i) Completeness: we aim to execute queries and get complete results over all data stored by the community. (ii) Autonomy: participants only host data they want and there is no routing. In this context, solving the discovery problem is to guarantee that each participant can discover all other participants. We consider a random abstract service able to return a random participant among the community. Such random service is enough to enable discovery. This service can be implemented in a decentralized fashion relying on random peer sampling techniques [START_REF] Kermarrec | Gossiping in distributed systems[END_REF]. Consequently, participants only collaborate to return a random node in the set of nodes. To build a query engine according to this model, we follow a bottom-up query evaluation strategy [START_REF] Ladwig | Linked data query processing strategies[END_REF]; sources description are not available and the query engine discovers new sources incrementally and terminates when all sources or a priori-decided proportion of sources have been processed. The Qasino approach allows not only to discover new sources during queries evaluation but also to discover other participants running similar queries. In this case, queries can collaborate to speed up query termination.

Qasino Nodes Data Structures

We consider a community of participants as a set of n nodes, n is unknown to participants. A node has a local data structure and a shared one defined as follows.

Definition 1 (Local Structure). A node N i has access to:

n, a statistical estimator of the number of nodes.

rand, a function generating independent and uniformly distributed random variables from the set of nodes, i.e. each time the node calls rand(), it gets a random node.

-D i , a local RDF dataset. -Q i , a SPARQL query. For each triple pattern tp of Q i , Q i [tp] stores the set of

mappings of the variables of tp.

A set of nodes {N 1 , . . . N n } defines a virtual dataset D defined as D = ∪ n i=1 N i .D i , i.e. D is the union of local RDF datasets. For simplicity, in this work we suppose that D i is immutable and a node executes only one SPARQL query, this can be easily extended to a set of queries.

Definition 2 (Remote Interface). A node N i exposes to other nodes:

-• , evaluation function as defined in [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF], i.e. for a triple pattern tp, N i . tp returns the set of mappings for the variables of tp that match the dataset D i . -E(tp), a boolean function that returns true if N i accepts to collaborate on the evaluation of tp, with tp ∈ Q i .

Qasino Query Processing Model

Each node maintains a local RDF data and can evaluate, at least, a triple pattern query. Query processing follows a bottom-up query evaluation strategy [START_REF] Ladwig | Linked data query processing strategies[END_REF]. This strategy does not assume source descriptions to be available before query execution and computes results in a bottom-up fashion. A SPARQL query Q i at a node N i is processed in the following steps: (1) Built a left-tree query plan of Q i . To determine the order of the evaluation of triple patterns, the cardinality of each triple pattern tp in Q is estimated using variable counting [START_REF] Stocker | Sparql basic graph pattern optimization using selectivity estimation[END_REF]. The most selective triple pattern is evaluated first.

(2) Evaluate Q's triple patterns over D i , the local dataset of N i (Q i [tp] ← N i . tp ).
N i has terminated, Q i [tp] = Q i D , i.e. Q i is evaluated over the virtual dataset D.
As nodes can only discover sources randomly, this makes the respect of both properties impossible. Among existing strategies for randomized algorithms are Las Vegas and Monte-Carlo algorithms. Las Vegas algorithms where the termination property is weakened to termination with probability 1, i.e. N i .execute returns with probability 1. Monte-Carlo algorithms ensure termination but completeness is replaced by the following guarantee: N i .execute returns Q i D with some probability ρ > 0 independent of n. Consequently, two termination conditions are possible: (1) All nodes are discovered, (2) A proportion p of nodes is discovered. Termination conditions impact the query completeness, i.e. evaluating the query over all nodes ensures answer completeness, this is not always the case for the second condition. Moreover, termination conditions impact the complexity of steps 3 and 4 of query processing.

Algorithms

In the following, we detail existing strategies for randomized algorithms and we propose a new collaborative randomize algorithm for SPARQL query processing. The proposed algorithm allows to speed up query termination while preserving the proportion of discovered nodes.

Discover All Nodes: Las Vegas algorithm Algorithm 1: Las Vegas SPARQL engine

Data:

V i ← {N i }: Set of visited nodes 1 Function N i .execute(): 2 while |V i | < n do 3 let N j ← rand() 4 if N j / ∈ V i then 5 foreach tp ∈ Q i do 6 Q i [tp] ← Q i [tp] ∪ N j . tp 7 V i ← V i ∪ {N j }
Algorithm 1 presents a Las Vegas algorithm for evaluating a SPARQL query Q i . For simplicity, we make the hypothesis that each node executes only one SPARQL query. Thanks to the random service, it may discover a new node at each iteration. If the discovered node has relevant data for the query, the query execution will produce new query results. Assuming the estimator n returns the exact number of nodes, consequently, it always produces correct and complete results, but its running time complexity is non-deterministic and it only terminates with probability 1. The main issue is to evaluate how many draws, in average, are necessary to get complete results. Such problem is similar to the coupon collector problem [START_REF] Myers | Some new aspects of the coupon collector's problem[END_REF]. The average complexity is:

n i=1 n i = n × (ln(n) + γ) + O(1)
iterations, where γ ≈ 0.577 is the Euler-Mascheroni constant.

To illustrate, consider n = 1000 nodes, a node executing a query Q i should try around 7484 random call to rand() in order to discover all nodes.

This algorithm raises several issues: (i) It requires that the exact number of nodes is known and immutable, which is not realistic in a decentralized setting. If n is overestimated by n, then the algorithm does not terminate. Conversely, if n is underestimated by n, then the results may be incomplete. (ii) As illustrated, discovering all the nodes can be very costly, especially discovering the last missing nodes.

Discover a Proportion of

4 if N j / ∈ V i then 5 foreach tp ∈ Q i do 6 Q i [tp] ← Q i [tp] ∪ N j . tp 7 V i ← V i ∪ {N j }
Instead of discovering all the nodes, a user can decide to stop the exploration after a given number k of random draws, for example 2n draws, hoping to discover as many sources as possible. Algorithm 2 describes a Monte-Carlo algorithm for executing a query Q i , based on this strategy.

Ideally, the user would decide to explore a proportion p of the nodes, for example only 99% of nodes to terminate. The main issue is to calibrate k such that, in average, the algorithm will discover p × n sources. Surprisingly, for a given p, the necessary number of draws is linear in n, as we will now detail.

Let us first compute the expected proportion u n (k) of the sources that have yet to be discovered after k draws, among n sources. Initially, no source has been discovered, so u n (0) = 1. During the k th draw, a new source is discovered with

probability 1 n u n (k), so u n (k + 1) = u n (k) -1 n u n (k) = n-1 n u n (k). The solution to this geometric progression is u n (k) = n-1 n k .
The number k max of random participants that must be drawn in average to see a proportion p of the sources verifies the equation 1 -u n (k max ) = p, that is 1 -p = n-1 n kmax . This equation can be rewritten as

k max = ln(1-p) ln( n-1 n ) = ln( 1 1-p ) ln( n n-1 )
.

By the mean value theorem applied to function ln, there is an

x ∈ [n -1; n] such that ln n n-1 = 1
x . In other words, k max = x ln 1 1-p n ln 1 1-p , which gives the number of iterations in Algorithm 2.

To illustrate, consider a set of n = 1000 nodes and p = 99%, then Algorithm 2 requires 1000 * (ln(1/1 -0.99)) = 4605 random draws to terminate. Compared to the Las Vegas algorithm, for a given p, the runtime complexity of Algorithm 2 is linear in n, compared to O(n ln(n)) for Algorithm 1. Moreover, the Monte-Carlo algorithm supports that n is approximated.

New Monte-Carlo algorithm for Collaborative Query Processing

The random service allows to discover not only data but also other nodes running similar queries. Therefore, it is possible for queries to collaborate by sharing intermediate results and random draws. This allows to speed up query termination while preserving the proportion of discovered nodes.

2 while ∃tp ∈ Q i : l k i [tp][l] < n × ln 1 1-p do 3 let N j ← rand() 4 foreach tp ∈ Q i do atomically 5 k i [tp][i]++ 6 if N j .E(tp) then 7 N i .sync(tp, N j .sync(tp, Q i [tp], V i [tp], k i [tp] )) 8 else if N j / ∈ V i [tp] then 9 Q i [tp] ← Q i [tp] ∪ N j . tp 10 V i [tp] ← V i [tp] ∪ {N j } 11 Function N j .sync(tp, M i , V i , k i ): 12 Q j [tp] ← Q j [tp] ∪ M i 13 V j [tp] ← V j [tp] ∪ V i 14 k j [tp] ← max(k j [tp], k i ) 15 return Q j [tp], V j [tp], k j [tp]
µ1 H1(µ1) -1 µ3 H1(µ3) 1 0 0 0 µ3 ⊕ µ1 H2(µ3) ⊕ H2(µ1) 0 3) Decode(IBLT2 -IBLT1): D2-1 = {µ1} D1-2 = {µ3} (c) Decoding all µ from the set difference IBLT 2 \ IBLT 1 Fig. 1: Computing N 1 .Q 1 [?x P1 ?y] ∪ N 2 .Q 2 [?
i [tp][]. k i [tp][j]
represents the number of draws that N j has participated for the computation of the triple tp, as known by

N i . k i [tp][i]
represents the number of draws that N i has participated for the computation of tp. Each time N i draws a random source, it increments its own number of random draws. For instance, k 1 [tp] = [1 → 3; 4 → 42] means that N 1 has done 3 draws from the computation of tp and it knows that N 4 has participated to 42 draws for the computation of tp. If a random node N j accepts to collaborate with N i on the evaluation of tp, they merge their shared counter by taking the max value for each cell. For example, if Consequently, the algorithm stops when this sum reaches k max . If we consider q nodes running the same query Q, then the lower bound to terminate for one node is in average n. ln(1/(1 -p))/q. As we can see, collaboration between q nodes can divide by q the number of random draws required to terminate.

N 2 .k 2 [tp] = [1 → 1; 2 → 73], then k 1 [tp]
Synchronizing sets of mappings. Synchronizing Q i [tp] (line 7) between nodes may become expansive when collaborative queries meet several times. Suppose two nodes N i and N j running queries that contain the same triple pattern tp. The sets of mappings of variables of tp N i .Q i [tp] and N j .Q j [tp] could be large as the query progresses, with potentially many duplicated mappings. This large number of mappings increases drastically the communication cost of sets synchronization. It is more efficient to exchange only missing mappings between nodes, especially, as nodes meet several time the set difference between the two sets of mappings gets smaller. Ideally, the communication between nodes should only depends on the size of the set difference rather than on the size of sets. In other words, considering two sets of mappings M i and M j where the set difference is

d = |M i \ M j | + |M j \ M i |, computing M i ∪ M j depends only on O(d) elements.
For efficient computation of set difference, we use a probabilistic data structure called Invertible Bloom Lookup Tables (IBLTs) [START_REF] Eppstein | What's the difference?: efficient set reconciliation without prior context[END_REF][START_REF] Goodrich | Invertible bloom lookup tables[END_REF]. Figure 1 illustrates how the set difference is computed using two IBLTs. Consider two nodes N 1 and N 2 running the same triple pattern tp : ?x p1 ?y. The evaluation of tp is the set {µ 1 , µ 2 } on the node N 1 with {µ 1 = {x → 7, y → 9}, µ 2 = {x → 4, y → 5}} and {µ 2 , µ 3 } on the node N 2 with {µ 2 = {x → 4, y → 5}, µ 3 = {x → 1, y → 2}}. Let H 1 and H 2 be two different hash functions. Figure 1a shows how N 1 computes IBLT 1 designed to handle 4 differences (d=4). µ 1 (then µ 2 ) is hashed with H 1 and H 2 , then assigned into two different cells. A cell is composed of three kinds of sum; keysum is the XOR sum of the keys (µ 1 ⊕ µ 2 ), HashSum is the XOR sum of the hashed keys (H 1 (µ 1 ) ⊕ H 2 (µ 2 )), and count is the number of elements assigned to the cell. When N 1 meets N 2 , N 1 sends IBLT 1 to N 2 . Then N 2 computes the set difference IBLT 2 \ IBLT 1 resulting in two different sets of mappings: (1) D 2-1 = {µ 3 } which is the missing set of mappings for node N 1 (2) and, D 1-2 = {µ 1 } which is the missing set of mappings for node N 2 . Then, N 2 can send back the response to

N 1 containing D 2-1 .
Sending only the difference reduces considerably the traffic between collaborative nodes. However, as IBLTs' is a probabilistic structure, its accuracy depends on the number of cells in the IBLT compared to the real number of differences between the two sets. If the number of cells is too small, then the IBLT cannot compute the missing mappings. Concretely, the decode operation will fail, so the exchange of IBLTs is useless. In this case, the node sends its set of mappings. In our context, as for cooperative nodes the difference gets smaller while the query progresses, IBLTs are eventually efficient as demonstrated empirically in the experimental study.

Experimental Study

We want to empirically answer the following questions: (1) Does the random service generate independent and uniformly distributed random variables? (2) How does visiting only a proportion of the sources impact queries answer completeness? (3) What is the impact of the number of collaborating queries on the number of iterations? (4) What is the impact of Invertible Bloom Lookup Tables (IBLTs) on traffic?

We implemented different software to achieve the experimental study. The code and experiments are available in the companion website3 .

Implementations

Query engines

The Qasino query engine is built on top of Apache Jena4 . We implemented a new customized symmetric hash join operator that integrates IBLTs.

Qasino simulator Decentralization raises the problem of running experiments with thousands of nodes. Deploying thousands of endpoints connecting, them with structured or unstructured network, measuring the traffic and the number of calls is intractable with a traditional experimental setup in federated query processing. To handle this issue, we deploy Qasino in PeerSim [START_REF] Montresor | PeerSim: A scalable P2P simulator[END_REF] to run experiments. PeerSim is configured to run in "cycles". In one cycle, each node executes synchronously several iterations of its execute function as described in the algorithms: Las Vegas, Monte-Carlo and Monte-Carlo collaborative. Therefore, we measure how many cycles (iterations) are necessary to get complete answers for queries and how many cycles are necessary to terminate, i.e. it is possible to get a query complete answers before the termination of the algorithms.

Random service Different approaches exist for implementing a decentralized random service [START_REF] King | Choosing a random peer[END_REF] and for network size estimators [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF]. We use Spray [START_REF] Nédelec | An adaptive peersampling protocol for building networks of browsers[END_REF] because Spray integrates a network size estimator and implements the random service on an unstructured network. Each Spray node has a logarithmic subset of the whole network as direct neighbors.

Experimental setup

Machine We run experiment on a HPCS computer Xeon(R) CPU E5-2680v2@2.80GHz with 160 cores and 130GB RAM.

Queries and dataset As the size of the dataset does not impact the number of cycles necessary for terminating a query, we use the dataset Diseasome5 . We generated 100 random queries from the dataset using PATH and STAR shaped templates with two to eight triple patterns instantiated with random values from the dataset. The triple patterns of these 100 queries selects 70417

Experimental results

Does the random service generating independent and uniformly distributed random variables?

To answer this question, we compare the theoretical complexity (dashed line) with the empirical complexity (solid line). Figure 3a presents the number of random calls for varying number of nodes for the Las Vegas Algorithm. Compared to n(ln(n) + γ), as computed in section 4.1, the experimental values denote a slight deterioration of the complexity around 5%. Figure 3b presents the proportion of visited nodes for different values of p and n = 1000. As expected the proportion of visited nodes is close to p.

Consequently, the experimentation confirms that the implementation of Qasino respects the theoretical model.

How does visiting only a proportion of the sources impact queries answer completeness?

We run several experimentations with the five queries of Table 2 with the Las Vegas algorithm. Only one node executes a query during an experimentation. Figure 4 presents the average of 100 executions per query. The stop bar Fig. 4: The impact of the proportion of visited nodes p on queries answer completeness chart represents the average number of iterations necessary to terminate the query with standard deviation. The complete bar chart represents the average number of iterations required to obtain complete result per query. As we can see, the number of iterations to terminate is higher than the number of iterations to get complete results. Moreover, for a proportion of visited sources equal to p = 0.99, the Monte-Carlo algorithm terminates with complete results in less than 4500 iterations. All node run the same query. We repeat the experiment for different number of collaborative queries. the same query. The IBLTs are configured for a number of differences < 500. Figure 6a shows the results for the query Q87. As the number of results per triple pattern is low (<500), the IBLT ensures optimal transfer, i.e. the number of transferred triples remains the same even if more queries collaborate. Figure 6b shows the results for the query Q73. As the query Q73 has much more intermediate results, IBLTs configured to handle only 500 differences can fail and trigger complete transfer between 2 collaborative queries.

As collaborative queries eventually converge, IBLTs are eventually efficient and we can observe that the number of transferred triples remain stable after 50 collaboratives queries.

Conclusion

In this paper, we proposed Qasino, an original decentralized collaborative model for discovering RDF datasources and executing SPARQL queries. In contraste to traditional P2P models, Qasino respects the autonomy of participants. Qasino is based on P2P model where the cost of discovery is not shared by default and queries execution deliver complete results. Qasino approach allows to discover relevant sources, similar running queries and share intermediate results. With such collaborative query processing, participants only store data they want and therefore, preserve their autonomy. This work opens several perspectives. First, in the model, we relied on the network size estimator based on the random service. The knowledge of visited nodes and the number of random draws should allow to build a termination strategy that is independent of the size of the network. Second, we applied a simple strategy with IBLTs to synchronize queries, we can improve this strategy for better optimization of traffic. Finally, decentralization raises issues on completeness, autonomy and performance. We conjecture that only 2 of these 3 properties can be achieved in a system.

2 : 2 for k from 1 to n × ln 1 1-p do 3 let

 2213 Nodes: A Monte-Carlo Algorithm Algorithm Monte-Carlo SPARQL engine Require: p < 1: Expected proportion of sources observed during a run Data: V i ← {N i }: Set of visited nodes 1 Function N i .execute(p): N j ← rand()

Algorithm 3 :

 3 Collaborative Monte-Carlo SPARQL engine Require: p < 1: Expected proportion of sources observed during a run Data: V i [tp] ← {N i }: set of visited nodes by a node searching tp k i [tp][j]: number of iterations by the node N j searching tp. 1 Function N i .execute(p):

Algorithm 3 extends

 3 Algorithm 2 to handle collaborative query processing. Compared to Algorithm 2, the local variablesQ i [tp], V i and k i are replaced in Al-Encode µ1 = {x → 7, y → 9} µ2 = {x → 4, y → 5} Computing IBLT 1 for N1.Q1[?x P1 ?y] Encode µ2 = {x → 4, y → 5} µ3 = {x → 1, y → 2} Computing IBLT 2 for N2.Q2[?x P1 ?y]2) Difference: IBLT2 -IBLT1, where W ⊕ W =

and k 2

 2 [tp] are updated with [1 → 3; 2 → 73; 4 → 42]. The sum of this vector, 3 + 73 + 42 is the number of random draws done by nodes N 1 , N 2 and N 4 to obtain the triple pattern in Q 1 [tp]. More precisely, N 1 .Q 1 [tp] contains the results obtained by N 1 in 3 draws, N 2 in 73 draws and N 4 in 42 draw, i.e. N 1 takes advantages of visited nodes by N 2 and N 4 .

Fig. 2 :

 2 Fig. 2: Five queries with the number of Triples, cardinalities and results per query

Fig. 3 :

 3 Fig. 3: Random Evaluation

Fig. 5 :Fig. 6 :

 56 Fig. 5: Collaborative Monte-Carlo algorithm, p = 0.97 for different number of collaborative queries

  The evaluation relies on the pushed-based symmetric hash join operator[START_REF] Ladwig | Linked data query processing strategies[END_REF], i.e. results are produced as soon as input tuples are available and input tuples can arrive on all inputs in any order. (3) Discover a source randomly N j , among the nodes. N j evaluates Q's triple patterns, as detailed in the different algorithms in the next sections. (4) Receive partial results from N j (only if N j has results), add partial results to hash table of the corresponding triple pattern and produce results (if available). In Qasino, source discovery is an integral part of the query processing. Sources are discovered online, and query results are produced incrementally.Problem statement: Given a set of nodes {N 1 , . . . N n }, our objective is to define a query execution function execute that ensures query termination and answer completeness. ∀N i ∈ {N 1 , . . . N n }, we expect: (i) Termination N i .execute eventually returns.

(ii) Completeness After a node

https://github.com/folkvir/qasino-simulation

https://jena.apache.org

https://old.datahub.io/dataset/fu-berlin-diseasome

Acknowledgements

This work was partially funded by the French ANR projects O'Browser (ANR-16-CE25-0005-01) and DeKaloG (ANR-19-CE23-0014-01). Mr. Grall is funded by the GFI company, Nantes, France.


Ismail Badache
email: badache@irit.fr

Mohand Boughanem
email: boughanem@irit.fr

Document Priors Based On Time-Sensitive Social Signals

Keywords: Social Information Retrieval, Social Signals, Signal Time, Resource Publication Date, Social Ranking, Language Models

Relevance estimation of a Web resource (document) can benefit from using social signals. In this paper, we propose a language model document prior exploiting temporal characteristics of social signals. We assume that a priori significance of a document depends on the date of users actions (social signals) and on the publication date (first occurrence) of the document. Particularly, rather than estimating the priors by simply counting signals related to the document, we bias this counting by taking into account the dates of the resource and the action. We evaluate our approach on IMDb dataset containing 167438 resources and their social data collected from several social networks. The experiments show the interest of temporally-aware signals at capturing relevant resources.

Introduction

Web search engines are expected to return relevant search results for a query. Classic notions of relevance focus on textual relevance. Recently, majority of search engines include social signals (e.g. +1, like) as non-textual features to relevance. However, in the existing works signals are considered time-independent. They are taken into account by only counting the signal frequency on a resource.

In this paper, we hypothesise that signals are time-dependent, the date when the user action has happened is important to distinguish between recent and old signals. Therefore, we assume tha the recency of signals may indicate some recent interests to the resource, which may improve the a priori relevance of document. Secondly, number of signals of a resource depends on the resource age. Generally, an old resource may have much more signals than a recent one.

We introduce the time-aware social approach that incorporates temporal characteristics of users' actions as prior in the retrieval model. Precisely, instead of assuming uniform document priors in this retrieval model, we assign document priors based on the signals associated to that document biased by both the creation date of the signals and the age of the document. Research questions addressed in this paper are the following:

1. How to take into account signals and their date to estimate the priors? 2. What is the impact of temporally-aware signals on IR system performance? The remainder of this paper is organized as follows. Section 2 reviews some related work. Section 3 presents details of our approach. In section 4, we describe our experiments. Finally, we conclude the paper and announce some future work.

Related Work

While considerable work has been done in the context of temporal query classification there is still lack of user studies that would analyze users' actions in temporal search from diverse viewpoints. Major existing works [START_REF] Badache | Social priors to estimate relevance of a resource[END_REF][START_REF] Chelaru | How useful is social feedback for learning to rank youtube videos?[END_REF] focus on how to improve IR effectiveness by exploiting users' actions and their underlying social network. For instance, Chelaru et al. [START_REF] Chelaru | How useful is social feedback for learning to rank youtube videos?[END_REF] study the impact of social signals (like, dislike, comment) on the effectiveness of search on YouTube. Badache and Boughanem [START_REF] Badache | Social priors to estimate relevance of a resource[END_REF] show the impact of different signals individually and grouped.

The works that are most related to our approach include [START_REF] Inagaki | Session based click features for recency ranking[END_REF][START_REF] Khodaei | Temporally-aware signals for social search[END_REF], which attempt to improve ranking in Web search. Inagaki et al. [START_REF] Inagaki | Session based click features for recency ranking[END_REF] propose a set of temporal click features, called ClickBuzz, to improve machine learning recency ranking by favoring URLs that have been of recent interest for users. Khodaei and Alonso [START_REF] Khodaei | Temporally-aware signals for social search[END_REF] propose incorporating time as aspect when investigating social search. They categorized user social interests into five classes: recent, ongoing, seasonal, past and random, and then analyzed Twitter and Facebook data on users activities.

Our work has a similar motivation as those previous efforts, i.e., harnessing any temporal features around a resource to improve relevance ranking of conventional text search. However, our approach is based on novel characteristics which are incorporated into language model. Our goal is to estimate the significance of a resource by taking into account the signal recency and the age of the resource.

Time-Aware Social Signals

Our approach focuses on the temporal dimension of users' actions. We rely on language model to model temporally-aware signals as a prior probability.

Preliminaries and Context

Social information that we exploit within the framework of our model can be represented by 5-tuple < U, R, A, T, SN > where U, R, A, T, SN are finite sets of instances: Users, Resources, Actions, Times and Social networks. 1. The history of each social action, let T ai ={t 1,ai , t 2,ai ,..t k,ai } a set of k moments (datetime format) at which action a i was produced, noted t k,ai . 2. Age of resource, let T d ={t D1 , t D2 ,..t Dn } a set of n dates (datetime format) at which each resource D was published, noted t D .

Resources. We consider a collection

Query Likelihood and Document Priors

We exploit language models [START_REF] Ponte | A language modeling approach to information retrieval[END_REF] to estimate the relevance of document to a query. The language modelling approach computes the probability P (D|Q) of a document D being generated by query Q as follows:

P (D|Q) rank = P (D) • P (Q|D) = P (D) • wi∈Q P (w i |D) ( 1 )
P (D) is a document prior i.e. query-independent feature representing the probability of seeing the document. The document prior is useful for representing and incorporating other sources of evidence to the retrieval process. w i represents words of query Q. Estimating of P (w i |D) can be performed using different models (Jelineck Mercer, Dirichlet) [START_REF] Ponte | A language modeling approach to information retrieval[END_REF]. The main contribution in this paper is how to estimate P (D) by exploiting social signals.

Estimating Time-Aware Priors

According to our previous approach [START_REF] Badache | Social priors to estimate relevance of a resource[END_REF], the priors are estimated by a simply counting of actions performed on the resource. We assume that signals are independent, the general formula is the following:

P (D) = ai∈A P (a i ) ( 2 )
P (a i ) is estimated using maximum-likelihood:

P (a i ) = Count(a i , D) Count(a • , D) (3)
To avoid Zero probability, we smooth P (a i ) by collection C using Dirichlet. The formula becomes as follows:

P (D) = ai∈A Count(a i , D) + μ • P (a i |C) Count(a • , D) + μ (4) P (a i |C) is estimated using maximum-likelihood: P (a i |C) = Count(a i , C) Count(a • , C) (5)
Where We assume that this simple counting of signals may boost old resources compared to recent ones, because resources with long life in the Web has much more chance to get more signals than recent ones. In addition, we assume that resources that have recent signals are more likely to interest user. We propose to consider the dates associated with a signal and the creation of a resource. To estimate priors, we distinguish two ways to handle it: a. By considering time of signal: we assume that a resource associated with fresh (recent) signals should be promoted comparing to those associated with old signals. Each time a given signal appears, it is associated with its occurrence time. Therefore, instead of counting each occurrence of a given signal, we bias the counting, noted Count ta , by the date of the occurrence of the signal.

Count ta (t j,ai , D) = k j=1 f (t j,ai , D) = k j=1 exp - t current -t j,ai 2 2σ 2 (6)
Where: f (t j,ai , D) represents signal-time function, we use Gaussian Kernel [START_REF] Phillips | A gentle introduction to the kernel distance[END_REF] to estimate a distance between current time t current and t j,ai with σ ∈ R + .

The prior P (D) is estimated using formula 4 but by replacing Count() by Count ta (). Notice that if the signal time is not considered f (t j,ai , D) = 1 ∀t j,ai . b. By considering the age of resource: the resource publication date plays an important role on the social life of this resource, i.e. an old resource has a greater chance to have a large number of interactions compared to a recently published resource. So to cope with this issue we propose to normalize the distribution of signals associated with a resource through resource publication date. We divide the number of signals by the current lifespan of the resource.

Count tD (a i , D) = Count(a i , D) Age(D) = Count(a i , D) exp -tcurrent-tD 2 2σ 2 (7)
The prior P (D) is estimated using formula 4 but by replacing Count() by Count tD () for document and Count tC () for collection.

Experimental Evaluation

To evaluate our approach, we conducted a series of experiments on IMDb dataset. The baseline is a retrieval process without using document priors. Our main goal in these experiments is to evaluate the impact of temporally-aware signals on IR.

Description of Test Dataset

We used a collection IMDb documents provided by INEX 1 . Each document describes a movie, and is represented by a set of metadata, and has been indexed according to keywords extracted from fields [START_REF] Badache | Social priors to estimate relevance of a resource[END_REF]. For each document, we collected specific social data via their corresponding API of 5 social networks listed in table 1. The nature of these social signals is a counting of each social actions on the resource. We chose 30 topics with their relevance judgments provided by INEX IMDb 2011 2 . In our study, we focused on the effectiveness of the top 1000 results. Table 1 shows an example of a document with their social data. Unfortunately, the date of the different actions are not available except the last date of Facebook actions (comment and share). Therefore, we represent results using formula 6 biased only by the last date of comment and share.

Result and Discussion

We conducted experiments with models based only on documents (Lucene Solr model and Hiemstra language model without prior [START_REF] Hiemstra | A linguistically motivated probabilistic model of information retrieval[END_REF]), as well as approaches combining textual content and social features with temporal aspects as prior of document. We note that the best value of μ ∈ [90, 100].

Tables 2 summarizes the results of precision@k for k ∈ {10, 20}, nDCG (Normalized Discounted Cumulative Gain) and MAP. We evaluated different configurations, by taking into account social actions, actions time (labeled signal Ta ) and resource age (labeled signal TD ). We have already shown that exploiting timeindependent signals as prior improve search. In order to check the significance of the results, we performed the Student test and attached * (significance against baselines) to the performance number of each row in the table 2 when the p-value is 0.05 confidence level, compared to the corresponding baselines results.

First, we investigate the retrieval performance attainable by considering the action time, in our case date of last comment and share. Table 2 (With Considering Action Time) shows that the nDCG and precisions are in general slightly better than the nDCG and precision scores where action time is ignored, but remain very comparable. Second, we investigate the retrieval performance attainable by considering the publication date of resource.Table 2 (With Considering Age of Resource) shows that the nDCG and precisions are in general better than the nDCG and precision scores where publication date is ignored (Without Considering Time). Finally, the best results are obtained by (All Criteria TD ) run with considering the publication date. Therefore, publication date factor is the most effective temporal aspect to enhance a search. Concerning date of signals, we did not really evaluated the real impact of the proposal because of the lack of suitable data (dates of different actions). We exploited only the date of the last action which is not enough to draw effective conclusion.

Conclusion

In this paper, we studied the impact of time related to users' actions and resource on IR. We proposed to estimate a social priors of a document by considering the time of the action and the publication date of the resource. Experiments conducted on IMDb dataset show that taking into account social features and temporal aspects in a textual model improves the quality of returned search results. The main contribution of this work is to show that time of user's action and the ratio of signals are fruitful for IR systems. An important issue that we did not address is the exploitation of times associated for each action. Unfortunately, currently social networks APIs do not allow extraction of these informations. For future work, we plan to estimate the impact of signals diversity with respect of their ages. Further experiments on another dataset are also needed.

  C ={D 1 , D 2 ,...D n } of n documents. Each document D can be a Web page, video or other type of Web resources. We assume that resource D can be represented both by a set of textual keywords D w ={w 1 , w 2 ,...w z } and a set of social actions A performed on D, D a ={a 1 , a 2 ,...a m }. Actions. We consider a set A={a 1 , a 2 ,...a m } of m actions (signals) that users can perform on resources. These actions (e.g. like, share, comment on Facebook) represent the relation between users U ={u 1 , u 2 ,...u h } and resources C. Time. Time T represents two types of temporal dimensions:

  : P (D) represents the a priori probability of D. Count(a i , D) represents number of occurrence of action a i on resource D. a • is the total number of social signals in document D or in collection C.

Table 1 .

 1 Instance of document with social data

				Facebook		Google+ Delicious Twitter LinkedIn
	Film Title	Id	Like	Share	Comment	+1	Bookmark Tweet	Share
	Sinister tt1922777 14763	13881	22914	341	12	2859	14
					Facebook
	Film Title	Id	Last Share	Last Comment	Publication Date
	Sinister tt1922777 2014-09-29T02:49:01 2014-09-28T00:41:01	2011-05-07T19:00:57

Table 2 .

 2 Results of P@k for k ∈ {10, 20}, nDCG and MAP Bookmark 0.3730 0.3414 0.4621 0.2600 Bookmark T D 0.3732 0.3427 0.4671 0.2618 Share (LIn) 0.3739 0.3432 0.4566 0.2515 Share T D (LIn) 0.3762 0.3449 0.4606 0.2542 All Criteria 0.4408 0.4262 0.5974 0.3300 All Criteria T D 0.4484 * 0.4305 * 0.6200 * 0.3366 *

	IR Models P@10 P@20 nDCG	MAP	IR Models	P@10 P@20 nDCG MAP
	Baselines: Without Priors		With Considering Action Time Ta
	Lucene Solr 0.3411 0.3122 0.3919 0.1782	Share Ta	0.4148 * 0.3681 * 0.5472 * 0.2970 *
	ML.Hiemstra 0.3700 0.3403 0.4325 0.2402	Comment Ta 0.3861 * 0.3601 * 0.5207 * 0.2844 *
	Baselines: Without Considering Time [1]	With Considering Publication Date TD
	Like	0.3938 0.3620 0.5130 0.2832	Like T D	0.4091 * 0.3620 * 0.5308 * 0.2907 *
	Share	0.4061 0.3649 0.5262 0.2905	Share T D	0.4177 * 0.3721 * 0.5544 * 0.2989 *
	Comment 0.3857 0.3551 0.5121 0.2813	Comment T D 0.3912 * 0.3683 * 0.5285 * 0.2874 *
	Tweet	0.3879 0.3512 0.4769 0.2735	Tweet T D	0.3918 * 0.3579 * 0.4903 * 0.2779 *
	+1	0.3826 0.3468 0.5017 0.2704	+1 T D	0.3900 0.3511 0.5246 0.2748

https://inex.mmci.uni-saarland.de/tracks/dc/2011/

https://inex.mmci.uni-saarland.de/tracks/dc/2011/


-Social data from 5 social networks: Like, Share and Comment (Facebook); Tweet (Twitter); +1 (Google+); Bookmark (Delicious); Share (LinkedIn).

• Results

Experimental Evaluation

• Majority of search engines include social signals (e.g. +1, like) as non-textual features to relevance. However, in the existing works signals are considered timeindependent.

• Hypothesis 1: signals are time-dependent, the date when the user action has happened is important to distinguish between recent and old signals. Therefore, the recency of signals may indicate some recent interests to the resource, which may improve the a priori relevance of document. • Hypothesis 2: the number of signals of a resource depends on the resource age, an old resource may have much more signals than a recent one.

• Research questions are the following:

1. How to take into account signals and their date to estimate the priors? 2. What is the impact of temporally-aware signals on IR system performance?

• We propose to consider the date associated with a signal and the age of a resource.

To estimate priors, we distinguish two ways to handle it:

• Proposal 1: Time of Signal

Resource associated with fresh signals are more likely to interest user and should be promoted comparing to those associated with old signals. Therefore, instead of counting each occurrence of a given signal, we bias the counting, noted 𝐶𝑜𝑢𝑛𝑡 𝑡 𝑎 , by the date of the occurrence of the signal.

Where 𝑓 𝑡 𝑗,𝑎 𝑖 , 𝐷 represents signal-time function, we use Gaussian Kernel to estimate a distance between current time 𝑡 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 and 𝑡 𝑗,𝑎 𝑖 with 𝜎 ∈ ℜ + . k represents the number of moments (datetime) at which action 𝑎 𝑖 was produced.

• 𝑷 𝑫 is estimated using formula 3 but by replacing 𝐶𝑜𝑢𝑛𝑡() by 𝐶𝑜𝑢𝑛𝑡 𝑡 𝑎 ().

Notice that if the signal time is not considered 𝑓 𝑡 𝑗,𝑎 𝑖 , 𝐷 = 1 ∀𝑡 𝑗,𝑎 𝑖

• Proposal 2: Age of Resource

The simple counting of signals may boost old resources compared to recent ones, because resources with long life in the Web has much more chance to get more signals than recent ones. So to cope with this issue we propose to normalize the distribution of signals associated with a resource through resource publication date. We divide the number of signals by the current lifespan of the resource.

• The prior 𝑷 𝑫 is estimated using formula 3 but by replacing 𝐶𝑜𝑢𝑛𝑡() by 𝐶𝑜𝑢𝑛𝑡 𝑡 𝐷 () for document and 𝐶𝑜𝑢𝑛𝑡 𝑡 𝐶 for collection.

Introduction

• We exploit language model to estimate the relevance of document D to a query Q.

• 𝑷 𝑫 is a document prior. 𝑤 𝑖 represents words of query Q. Estimating 𝑃 𝑤 𝑖 𝑄 can be performed using different models.

• The priors are estimated by a counting of actions 𝑎 𝑖 performed on D.

With 𝑃(𝑎 𝑖 ) is estimated using maximum-likelihood:

• We smooth 𝑃(𝑎 𝑖 ) by collection C using Dirichlet :

With 𝑃(𝑎 𝑖 |𝐶) is estimated using maximum-likelihood:

Where 𝑷 𝑫 represents the a priori probability of D. 𝐶𝑜𝑢𝑛𝑡(𝑎 𝑖 , 𝐷) represents number of occurrence of action 𝑎 𝑖 on resource D. 𝑎 • is the total number of social signals in document D or in collection C.

Time-Independent Social Signals

  IMDb Topics and their relevance judgments.

  Fig. Global presentation of our approach


Ismail Badache

Social Signals: Any Impacts in Search?

Keywords: Any Impacts in Search? Badache, Mohand Boughanem Information Retrieval, Social Signals, Popularity, Reputation, Freshness, Diversity, Ranking ►Context

come

Introduction

Table 1 .

 1 Exploited social signals in quantification