On searching and integrating various kinds of open data, one of crucial issues is to efficiently find sufficient SPARQL endpoints that store sufficient data to be retrieved in the query. In this demonstration, we will present our online learning-based efficient search algorithm and our prototype implementation based on an extended multi-armed bandit approach, which takes into account how the demanded data could be stored in each SPARQL endpoint by the results obtained from a series of test queries.
At the beginning of 2014, we have over 500 of information sources known as endpoints
of Linked Open Data(LOD)∗. To utilize such endpoints effectively, we often make some
federated queries to some of useful endpoints available in the world. It is not an easy
task to accurately predict which endpoints could be helpful to be used for the queries,
since there are so many endpoints and also those endpoints are dynamically updating
their data but little information are given about how their stored data are useful for the
queries[
To examine how an endpoint is useful and appropriate for a given query, we need to pre-check how each endpoint has useful data as well as how such data can be effective to retrieve further data stored in other endpoints. However, when we try to examine all the endpoints to be accessed at one time, it will cause serious network congestions due to its heavy network loads, as well as unwanted server loads in those endpoints. Therefore, we need to effectively predict the performance of possible endpoints to be used in a query. In this demonstration, we present a conceptual model of our online learning-based efficient search algorithm and our prototype implementation based on an extended multi-armed bandit approach, which takes into account how the demanded data could be stored in each SPARQL endpoint by the results obtained from a series of test queries. ∗http://sparqles.okfn.org/ the situation, the problem seeks how an algorithm can choose the best arm to obtain maximal revenues as well as the cost for estimating the revenue distributions of arms.
The Budget-Limited Multi-Armed Bandits(BLMAB) model[
The Extended BLMAB model for the end-point search problem(ESP) is an extended BLMAB model, which introduces a two-dimension cost constraint, i.e., the cost for network load and the cost for query execution time. In our extended BLMAB model, the player can choose an arbitrary number of arms from the total K arms to pull in each step. Each arm i has its cost ci to obtain the revenue based on an unknown distribution µi. The player has budget B so that the cost to be payed should be in the budget, and also the maximum steps is limited to be T ∈ N. The objective of the player is maximizing its revenue by choosing arm i with the limited budget B within the limited T steps. Therefore, we extend the original BLMAB constraints to the following: (1) (2) 3
On the end-point search problem, we can assign each endpoint as each arm in the extended BLMAB model. Here, often each endpoint has a limited number of variations in its effective exploration queries. Therefore, the extended BLMAB model should satisfy that, let Q be the number of variations in its exploration queries, an arm i should satisfy NiA(B) ≤ Q.
While the main objective of MAB is to maximize the total revenue, the main objective in end-point search problem is to find the best arm to be used for the final (but not exploration) query. Therefore, let i(A) be the best arm obtained from A, i(A∗) be the theoretically best arm, we re-define the regression function for our extended BLMAB model as follows:
P ! K " NiA(B)ci ≤ B ∩ t ≤ T #
= 1 i
Here, as described in [
R(A) = i(A∗) − i(A) 4
difference of objectives, since our model is based on an extended BLMAB Model. In Figure 4, the vertical axis shows the regression value defined in Equation 2. Notice that, less regression value is better in this context.
Figure 1 shows the overview of our prototype system, called SPARQL-MAB. We are implementing the two algorithms in the system ∗. Further evaluations and refinements about the models and algorithms are our future work.
For the preparation of the target query to be examined, an abstract query[
In Figure 3, two example queries are shown. Those queries were generated from the user’s query shown in Figure 2.
∗A demonstration is available at http://whitebear.cs.inf.shizuoka.ac.jp/sparql mab/
In this evaluation, we prepared a hundred of pseudo endpoints each of which stores 10 thousands of triples. Each triple is composed from a randomly selected concepts generated from a hundred kind of nouns or concepts in the given ontologies.