Paper 129 (Research track)

Intelligent clients for replicated Triple Pattern Fragments

Author(s): Thomas Minier, Hala Skaf-Molli, Pascal Molli, Maria-Esther Vidal

Full text: submitted version

camera ready version

Decision: accept

Abstract: Following the Triple Pattern Fragments (TPF) approach, intelligent clients are able to improve the availability of the Linked Data. However, data availability is still limited by the availability of TPF servers. Although some existing TPF servers belonging to different organizations already replicate the same datasets, existing intelligent clients are not able to take advantage of replicated data to provide fault tolerance and load-balancing.
In this paper, we propose Ulysses, an intelligent TPF client that takes advantage of replicated datasets to provide fault tolerance and load-balancing. By reducing the load on a server, Ulysses improves the overall Linked Data availability and reduces data hosting cost for organizations. Ulysses relies on an adaptive client-side load-balancer and a cost-model to distribute the load among heterogeneous replicated TPF servers. Experimentations demonstrate that Ulysses reduces the load of TPF servers, tolerates failures and improves queries execution time in case of heavy loads on servers.

Keywords: Semantic Web; Triple Pattern Fragments; Intelligent client; Load balancing; Fault tolerance; Data Replication

 

Review 1 (by Ruben Taelman)

 

(RELEVANCE TO ESWC) This article introduces a mechanism for TPF clients to exploit replication of datasets in different TPF servers, which is very relevant for a Semantic Web conference.
(NOVELTY OF THE PROPOSED SOLUTION) The authors introduce an algorithm for delegating triple pattern queries to different servers using an adaptive cost-model, which is based on related work, but is sufficiently novel in this context.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) The algorithms make sense and are explained in detail.
(EVALUATION OF THE STATE-OF-THE-ART) The relevant related work is mentioned.
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) An online demo is provided, and the approach is discussed in detail.
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) The experiments are sufficiently reproducible.
For completeness and reproducibility, the exact version and config files used for the LDF server should be included,
as I could not find them on GitHub.
Furthermore, I could not find the raw benchmark results that are used in the scripts to calculate the p-values.
(OVERALL SCORE) This article introduces a mechanism for TPF clients to exploit replication of datasets in different TPF servers.
The authors assume a catalog to be available that maps fragments to relevant servers.
How this catalog is obtained is out-of-scope for this work.
Based on this catalog, the authors introduce an algorithm for delegating triple pattern queries to different servers
using an adaptive cost-model.
Results (and the online demo) show that this approach is able to distribute load between servers that replicate the same dataset.
Furthermore, the approach is fault-tolerant when servers become unavailable at runtime.
My only main concern with this work is that no server cache was used in the evaluations.
In practise, most TPF servers have some kind of Web cache,
as the resources that are produced are highly cacheable,
which leads to lower server load.
It would be valuable to know what the effects of caching are compared to replication.
For example, would it be better to publish the dataset again of a different server? Or would adding a cache be more effective?
And what are the effects when replication and caching are combined.
Nevertheless, the current experiments are already very extensive,
and result in valuable conclusions.
So I would strongly recommend the authors to look into this in future work.
Other than that, the paper is very well written and the approach+algorithms
are understandable and described in detail with useful examples.
Next to that, extensive experiments were done and are (mostly) reproducible.
From these results, valuable conclusions were drawn.
In conclusion, this is strong work that deserves to be presented at the conference.
SP:
* Clear description and examples of approach
* Detailed experimental results
* Open-source code is provided
WP:
* The conclusions that are drawn from the Wilcoxon signed rank test are statistically incorrect. (see comments below)
* Not all required details on the experiments are provided.
* No Web cache is used in evaluations

 

Review 2 (by Alessandro Margara)

 

(RELEVANCE TO ESWC) The paper presents Ulysses, a client for Triple Pattern Fragments (TPF) that
exploits replication to provide adaptive load balancing and fault tolerance.
This is certainly interesting and relevant for the conference.
(NOVELTY OF THE PROPOSED SOLUTION) Although the approach is typical in distributed systems, I am not aware of
any similar solution for TPF.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) The solution is well defined and appears to be correct.
The authors currently ignore the effects of caching, which might influence the performance
of the proposed solution.
(EVALUATION OF THE STATE-OF-THE-ART) The analysis of background and related work is well organized.
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) The definitions are well supported by examples.
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) 1. The authors do not consider the effects of server caches (as explained in
Section 4.1 - Servers and client configuration). However, I believe that
simply disabling the HTTP cache can lead to unrealistic results. I suggest
that the authors include an experiment in which they measure the effects of
Web caches, maybe using different clients that continuously send queries
selecting from a pool of queries with various distributions.
2. The entire evaluation has been conducted on a single dataset: can the
dataset impact on the performance and benefits of Ulysses? I suggest that the
authors discuss this aspect, and possibly present some results with a
different dataset.
3. The queries adopted in the evaluation should be discussed in more details,
presenting some statistics on the number of results they produce.
(OVERALL SCORE) The paper presents Ulysses, a client for Triple Pattern Fragments (TPF) that
exploits replication to provide adaptive load balancing and fault tolerance.
The paper is well written and easy to read and understand. The analysis of
background and related work is well organized; the definitions are well
supported by examples; the evaluation is rigorous, with the experiment setup
and the results discussed in detail. The topic is interesting and relevant for
the community.
I have a few comments/suggestions:
1. The authors do not consider the effects of server caches (as explained in
Section 4.1 - Servers and client configuration). However, I believe that
simply disabling the HTTP cache can lead to unrealistic results. I suggest
that the authors include an experiment in which they measure the effects of
Web caches, maybe using different clients that continuously send queries
selecting from a pool of queries with various distributions.
2. The entire evaluation has been conducted on a single dataset: can the
dataset impact on the performance and benefits of Ulysses? I suggest that the
authors discuss this aspect, and possibly present some results with a
different dataset.
3. The queries adopted in the evaluation should be discussed in more details,
presenting some statistics on the number of results they produce.
4. The advantages that derive from using multiple servers in the case of load
are difficult to read. I suggest that the authors include a speedup graph for
x servers w.r.t. a single server, or at least include some speedup data in the
text.
---
Minor comments
Page 3: Moreever -> Moreover
Page 5: Let tp(D) denotes -> denote
Page 7: Patterns with more than one relevant fragments requires -> require
Page 7: is evaluated is in a constant time -> is evaluated in constant time
Page 10: Answer Completeness is not an evaluation metric, but rather a
correctness criterion. I suggest to remove it from the evaluation metrics and
only mention that the responses are always complete (identical to those of the
reference TCP client).
Page 11: hypothesis H0 is possibly wrong? Shouldn't it be the opposite?
Page 14: faults tolerance -> fault tolerance
Page 14: Ulysses accurately evaluate -> evaluates
Page 14: Ulyssesdistributes -> Ulysses distributes
---
Strong points
1) Relevant to the conference.
2) Novelty of the solution.
3) Well written.
4) Evaluation is rigorous and the results are discussed in details.
5) Interesting application of traditional solutions in distributed systems.
Weak points
1) The authors do not consider the effects of server caching.
2) The evaluation is conducted on a single dataset.
3) The queries adopted in the evaluation should be discussed in more details.
Questions
1) Can the authors elaborate more on the effects of server caching? Would it
be possible to introduce some experiment on the impact of caching?
2) The evaluation has been conducted on a single dataset. Can the dataset
impact on the performance and benefits of Ulysses? Would it be possible to
introduce experiments on different datasets?
3) Can the authors better present the queries adopted in their evaluation?
---
I'd like to thank the authors for answering my questions.

 

Review 3 (by Pieter Colpaert)

 

(RELEVANCE TO ESWC) This is a paper that I already reviewed for ISWC2017, then rejected. My comments are taken into account and my +1 review from then after rebuttal remains.
(NOVELTY OF THE PROPOSED SOLUTION) Parallellizing sparql queries over replicated datasets have not yet been done before. I still have questions to the usefulness of this on the Web, where I’d rather fix publishing interfaces than “hotfix” low availability or slow server interfaces by smarter source selection.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) The proposed solution has an implementation and a valid evaluation
(EVALUATION OF THE STATE-OF-THE-ART) State of the art on federated querying is mentioned, as well as the key work on Triple Pattern Fragments.
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) The paper comes with a very nice demonstrator at https://callidon.github.io/ulysses-tpf/
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) Using the code at https://github.com/Callidon/ulysses-tpf, the study is reproducible.
(OVERALL SCORE) For completeness, I include my review on the paper at ISWC2017 beneath. I do not have more questions to the authors.
This paper presents an approach to parallelize SPARQL query processing over triple pattern fragments servers that contain the same triples. QUARTZ -- as the authors call it -- uses metadata about TPF server in order to minimize query times and maximize load balancing. The work makes assumptions that I would like to challenge in the rebuttal phase.
I am not satisfied with the motivation of the paper to distribute parallel queries over multiple machines for the reason of availability/load balancing. TPF has been designed in order to maximize the reuse of their datasets, and is evaluated not to slow down under higher load ^2. A possible reason for balancing the load among multiple servers could maybe be privacy constraints? To that extent, I also do not understand why executing in parallel on 1 TPF server was not evaluated: won’t that be even faster? I tried this for the demo query using the quartz-tpf code and was indeed even faster... Can you elaborate on whether my assumption is correct/incorrect?
Abstract, introduction and in conclusion: last sentence of abstract says it significantly improves execution time of SPARQL queries. What is significantly and compared to what? ^1 (do add this in the final camera-ready!)
Section 3: assumption 4 seems dangerous - only when the same back-end is used this _might_ be true.
Subsection 3.2: an assumption (hypothesis?) is made that the access time does not depend on the evaluated triple pattern and that the time is constant per server for any triple pattern. TPF gets its scalability from caching. Why is cacheability not taken into account? Cached TPFs are going to return faster than TPFs that are not.
Section 4 Load balancing: In order to evaluate the load balancing, you test the number of HTTP requests per server. It would have been more interesting to see the real load that happened on these different servers. Judging from the TPF evaluations ^2, I think the server can handle the extra load without any problem. You could argue that sending multiple HTTP requests to one server will be queued by the server, yet this issue can be fixed by exploiting the HTTP protocol as such (e.g., by using cloud caches).
# __ After Rebuttal __
I decided to raise my score to +1 after rebuttal as my main questions were targeted. Nevertheless, following the reasoning of the other reviewers, I agree with the overall decision.
Still an issue with the paper is that the conclusions need work (among others in the abstract). At least it should include the argument about increased load in the motivation as formulated in the rebuttal.

 

Review 4 (by Catherine Faron Zucker)

 

(RELEVANCE TO ESWC) This paper presents an intelligent TPF client providing load balancing and fault tolerance over replicated TPF servers.
(NOVELTY OF THE PROPOSED SOLUTION) The proposed approach relies on a replication model which has already been published. The theoretical contribution consists in a cost model for evaluating TPF server capabilities, the adaptation of a state-of-the-art load distribution approach to access TPF servers based on their capabilities, and finally the development of a client-side load balancer which adapts to changes and provides tolerance.
(CORRECTNESS AND COMPLETENESS OF THE PROPOSED SOLUTION) The proposed approach has been implemented and empirically validated. The authors conducted a wide range of experiments. The experimental setup is impressive.
(EVALUATION OF THE STATE-OF-THE-ART) very pedagogical
(DEMONSTRATION AND DISCUSSION OF THE PROPERTIES OF THE PROPOSED APPROACH) The proposed approach has been implemented and empirically validated. The authors conducted a wide range of experiments. The experimental setup is impressive.
(REPRODUCIBILITY AND GENERALITY OF THE EXPERIMENTAL STUDY) The code and material are available online.
(OVERALL SCORE) This paper presents an intelligent TPF client providing load balancing and fault tolerance over replicated TPF servers. The proposed approach relies on a replication model which has already been published. The theoretical contribution consists in a cost model for evaluating TPF server capabilities, the adaptation of a state-of-the-art load distribution approach to access TPF servers based on their capabilities, and finally the development of a client-side load balancer which adapts to changes and provides tolerance. The proposed approach has been implemented and empirically validated. The authors conducted a wide range of experiments. The experimental setup is impressive. 
The paper is exemplary in its organization and writing, very pedagogical, it makes enjoyable reading.

 

Metareview by Ruben Verborgh

 

The reviewers are in agreement about the relevance and quality of this submission. As such, we recommend acceptance for ESWC2018.
Possible areas of improvement include the conclusion, which at the moment is largely a summary. Could you replace the summary by lessons learned? I.e., what does this mean for people setting up TPF interfaces? Should they focus on replication, and to what extent? Do all datasets need replication, or does it depend on size (or other factors)? It should be clear what your experimental findings in the end mean for the landscape of publishing and querying RDF on the Web.
Also, be careful when discussing availability. TPF by itself does not directly influence availability; rather, it decreases the cost for a certain server needed to obtain a given availability. In the context of replication, this means it might be cheaper/more meaningful to have n replicated TPF servers rather than one SPARQL endpoint.
Please also address the concern regarding the Wilcoxon test, and the exact versions of the software used, in order to ensure reproducibility. Also, please discuss the topic of external validity with regard to the tested dataset.

 

Share on

Leave a Reply

Your email address will not be published. Required fields are marked *