RDF graphs can be large and complex; finding out interesting information within them is challenging. One easy method for users to discover such graphs is to be shown interesting aggregates (under the form of two-dimensional graphs, i.e., bar charts), where interestingness is evaluated through statistics criteria. Dagger [5] pioneered this approach, however its is quite ineficient, in particular due to the need to evaluate numerous, expensive aggregation queries. In this work, we describe Dagger+, which builds upon Dagger and leverages sampling to speed up the evaluation of potentially interesting aggregates. We show that Dagger+ achieves very significant execution time reductions, while reaching results very close to those of the original, less eficient system.
∗M. Mazuran is supported by the H2020 research program under grant nr. 800192.
The problem of data exploration [
In [
In contrast, Dagger (and Dagger+) start directly from RDF, and, lacking schema information, automatically derives dimensions and measures that are good candidates to produce insights.
There is no universally accepted definition of interestingness;
frequently, something unexpected (which difers from a
reference) is considered interesting. The reference might be known
a-priori, come from historical data, or be the average behavior.
So far we have experimented with variance, skewness and
kurtosis; we are also working to use the entropy. Many diferent RDF
visualizations techniques can be used, e.g., [
We consider three pairwise disjoint sets: the set of URIs U, the set of literals L, and the set of blank nodes B. An RDF graph G is a finite set of triples of the form (s, p, o), called subject, property and object, such that s ∈ (U ∪ B), p ∈ U and o ∈ (U ∪ B ∪ L). The RDF property rdf:type is used to attach types (i.e. classes) to an RDF resource, which can have zero, one or several types. G can have an ontology stating relationships between its classes and properties, e.g., any UndegraduateStudent is a Student; its presence may lead to implicit triples, which are part of G even if they may not appear explicitly. A graph containing all the triples which may be derived from it is said to be saturated. Without loss of generality, we consider that our input graph is saturated.
Dagger identifies unidimensional aggregate queries to be evaluated in an RDF graph G. However, unlike a traditional relational data warehouse, an RDF graph comes without identified set of facts; nor are dimensions and measures known in advance. Therefore, Dagger must enumerate candidates for each of these roles.
A set of candidate facts (c f , in short) is a set of G resources which are deemed interesting for the analysis. Dagger considers as c f (i) all the resources of a given class C, e.g., all the Students; (ii) all the resources having a certain set P of properties, e.g., all those having title and author. A simple way to pick such a property set is to compute the support of the properties in G and select property sets whose support is above a certain threshold.
A candidate dimension (denoted d) is used for grouping the
candidate facts. Dagger supports as candidate dimensions (i)
properties present on at least a certain fraction tthr es of resources
from c f ; (ii) derived properties, computed by Dagger in order
to find potentially interesting insights. The derived properties
supported in [
A candidate measure (denoted m) is something to be evaluated or measured for each candidate fact. Dagger considers candidate measures among the (original or derived) properties of candidate facts whose support is above tthr esh . Dimension-measure combinations such that one is a property a and the other is the count a# of this property are excluded.
An aggregation function ⊕ is chosen among min, max, avg, sum, count; the first four are considered only if the measure is numeric. Given that RDF data is often untyped or only partially typed, Dagger implements a type detection mechanism by trying to convert the property values to diferent types.
A Dagger aggregate aдд is a tuple (c f , d, m, ⊕). To specify how interesting an aggregate is, let f (V ) be a function which inputs a set of numerical values V and returns a number. Given f , the interestingness of aдд is computed as: • let d1, d2, . . . be the distinct values that d may take for a resource in c f ; • for each di , let c fi be set of c f resources for which d takes the value di ; observe that the c fi sets may overlap, as a resource with more than one value for d belongs to several such sets. For instance, students can be grouped by the courses they take, and each student takes many courses; • for each c fi , let Mi be the set of m values of c fi resources, and mi = ⊕(Mi ); • the interestingness of aдд is f ({m1, m2, . . .}).
The problem considered by Dagger is: given a graph G, a set of value thresholds, function f and an integer k, find the k most interesting aggregates.
Architecture. Dagger leverages the robust query evaluation capabilities of an RDBMS to store the RDF graph, enumerate and evaluate candidate aggregates. SQL queries are used to: determine the resources part of a candidate fact sets; evaluate the suitability of their properties as dimensions, respectively, measures; compute and aggregate the group measures mi . The remaining operations, e.g., the computation of the interestingness score function, are done in Java.
Aggregate recommendation cost. The most expensive computation steps are: (i) finding the candidate dimensions and ( ii) evaluating the aggregation operations. Indeed, when looking for candidate dimensions, several queries are issued over c f (e.g., ifnd all distinct properties, count the number of subject that have each property, find the values of the derived properties, etc.). Moreover, many candidate aggregates are generated, also leading to a high number of potentially expensive SQL queries. 4
DAGGER+: SPEEDING UP DAGGER
A set of re-engineering changes were brought to Dagger since
the original demonstration. In particular, it has been ported on
top of OntoSQL (https://ontosql.inria.fr), a Java-based platform
developed at Inria, providing eficient RDF storage, saturation,
and query processing algorithms [
Further, we adapted an optimization previously proposed in [
Below, we focus on two novel optimization techniques we applied subsequently: using an RDF graph summary to speed up candidate dimension enumeration (Section 4.1), and using sampling to accelerate candidate dimension enumeration, aggregate evaluation and ranking (Section 4.2). 4.1
RDFQuotient [
We introduced two sampling strategies to trade some accuracy in aggregate selection for running time: • CFSampling: the c f is sampled (draw n1 samples of size n2), and candidate dimensions and measures are found for each sample independently. For each of the n1 samples, candidate aggregates are generated, and their interestingness is evaluated on the sample. • ESampling: candidate dimensions and measures are computed on the whole c f as in Dagger. Then, n1 samples of size n2 are drawn from the c f , and the candidate aggregates are evaluated on the samples.
With CFSampling, the aggregates recommended for diferent sample may be diferent, e.g., certain properties might be found to be frequent in some sample but not in all of them. After the evaluation, a ranked list of aggregates is obtained for each sample. In ESampling, instead, the set of aggregates is unique as it is derived directly from the original data. However, given that all the aggregates are evaluated on samples, it also yields a ranked list of aggregates for each sample.
To be able to compare the results found without sampling with those found through sampling, we need to reconcile the results found on diferent samples into a single ranked list. We can do this by taking (i) the union or (ii) the intersection of the lists obtained from all the samples. Then, we re-rank the aggregates according to a estimation of their global interestingness measure (based on their interestingness on each sample), e.g., through pooled variance; at the end of this process, we obtain a unique ranked list of candidate aggregates. 5
Sampling. We measure the running time and the accuracy of the results by varying 3 parameters: (i) the sampling strategy (CFSampling or ESampling), (ii) the number of samples (2, 3, 4 or 5); and (iii) the sample size, as a ratio of the candidate fact set size (from 1% to 10% of the number of distinct CF resources). Figure 3 shows the running times: one plot for each number of samples (from top to bottom, 2, 3, 4, 5), each of which varies the strategy and the sample size. Ten runs are averaged for each parameter combinations (diferent samples are drawn in each run).
Figure 3 shows that ESampling is slower than CFSampling, as the former looks for candidate dimensions on the whole candidate fact set, whereas the latter does this on smaller-size samples. ESampling enumerates all the candidate aggregates also found without sampling, while CFSampling might enumerate a diferent set of aggregates: some properties that are overall frequent (infrequent) might be found infrequent (frequent) in a specific sample, and thus not be considered (considered) as candidate dimensions and measures. However, even though ESampling enumerates all the no-sampling candidate aggregates, it evaluates them on samples, and may end up considering them interesting (uninteresting) diferently from the way they are on the complete CF.
To evaluate the accuracy of the results obtained through sampling, we compare the Top-5, Top-10 and Top-20 aggregates found without sampling, with those found through sampling. The ranked list of aggregates found with sampling is built by taking the union of all those found across the samples and reranking them according to the interestingness measure (in our experiments we use the pooled variance to rank all the results).
Top-K 1% 3% 5% 7% 9% 10%
Top5 28% 36% 28% 24% 24% 36% 2 Top10 41% 55% 54% 55% 62% 75%
Top20 57% 69% 80% 81% 88% 96%
Top5 32% 16% 28% 24% 36% 20% 3 Top10 49% 55% 60% 55% 74% 61%
Top20 57% 68% 74% 80% 85% 83%
Top5 32% 22% 16% 12% 20% 12% 4 Top10 46% 50% 39% 42% 50% 55%
Top20 63% 68% 72% 76% 81% 85%
Top5 40% 20% 24% 20% 16% 20% 5 Top10 55% 53% 50% 51% 49% 55%
Top20 67% 63% 68% 74% 78% 79% Table 1: Accuracy of results with CFSampling. there is a 10% diference in accuracy on average, i.e. the top-Ks difer by 2/3 aggregates. This does not mean that such aggregates were not found though but they have been ranked diferently.
Figure 4 plots the accuracy with respect to the running times. Each line of graphs represents the Top-5, Top-10 and Top-20 for a diferent number of samples; red x’s indicate CFsampling, while green +’s indicate ESampling, for diferent sample dimensions. Clearly, the accuracy increases with K (the amount of top aggregates) and with the size of the samples. The increase in the number of samples does not significantly improve accuracy.
Automatic selection of interesting aggregates in an RDF graph
is challenging, as candidate dimensions and measures must be
“guessed” from the data, and candidate aggregates must be
evaluated to assess their interestingness. After re-engineering
Dagger [