Knowledge about the distribution of data provides the basis for various tasks in the context of Linked Open Data, e.g. for estimating the result set size of a query, for the purpose of statistical schema induction or for using information theoretic metrics to detect patterns. In this paper I investigate the potential of obtaining estimates for such distributions from samples of Linked Data. Therefore, I consider three sampling methods applicable to public RDF data on the Web as well as smoothing techniques to overcome the problem of unseen events in the sample space of a distribution. In a systematic empirical evaluation I look into the effects of these techniques on the quality of distributions approximated from samples. The obtained insights help to assess the quality impact of combinations of sampling and smoothing techniques on five prototypical structures over which distributions are estimated. Furthermore, the results demonstrate the potential and the limitations of these techniques, motivating further work in the direction of sampling from Linked Open Data.
Estimating the distribution of instances in data storage systems plays an important role
for various applications. Query optimisation techniques rely on such information for
estimating the result set size for a query [
One reason might be the lack of a predefined schema which provides a clear
structure over which to estimate distributions of data items. Another reason might be the
difficulty to obtain sufficient data for reliable estimates of a distribution. However, recent
developments provide some techniques and solutions to these problems. For instance,
methods for schema induction and schema-level indices [
With this paper I would like to take a first step in this direction. Thus, I address two
of the challenges which will need to be solved for efficient and effective estimation of
distributions over Linked Data: sampling and smoothing. Both will play a major role
when dealing with distributions over Linked Data in the future. Sampling techniques
will be a key contributing factor as they enable large scale processing of Linked Data.
Given the recent growth rate of the Web of Data it is becoming less and less feasable
to analyse the entirety of all data published on the LOD cloud. Moreover, the dynamics
and change rate [
The second topic—smoothing—is closely related to sampling, but addresses another dimension of the problem. The liberty of data providers to model data as they please as well as the decentralised approach of everyone being able to add, change or remove data in an ad-hoc fashion will lead to a particular phenomenon: the sample space over which to model a distribution is not fixed but the events in this space are flexible and evolving. Take, for instance, the question of how data instances are distributed over RDF class types. At any time a data provider can come up with a new class type and start using it immediately to describe entities on the Web. Any distribution which has been obtained over previous data will not be aware of this class type. Accordingly any application making use of the distribution will operate with a zero probability. This causes problems in various contexts and applications (e.g. when performing an information theoretic analysis). The importance of this problem becomes even more obvious when introducing sampling approaches. Using only a small slice of the Linked Data cloud to estimate distributions over the entire data space will almost certainly mean that some rare combinations of data characteristics have not been observed in the sample. Smoothing techniques aim at overcoming this problem, by reserving some probability mass for unseen events.
Hence, given the importance of sampling and smoothing, in this paper I will consider three well established approaches for sampling Linked Data as well as smoothing techniques to overcome the problem of unseen events. The investigated distributions and their sample spaces of schema-level structures are taken from related work and represent typical information used in different application settings. The contribution of the paper at hand is therefore an analysis of the impact of different combinations of sampling and smoothing on estimating distributions over different types of schema structures. Furthermore, the paper provides a baseline for future work on more specific and sophisticated approaches for either sampling or smoothing techniques.
The remainder of the paper is structured as follows. I will formalise the data model used throughout the paper as well as the considered sampling techniques in Section 2. Subsequently, Section 3 gives an overview of schema-level structures which are frequently used as events in a sample space for estimating distributions over Linked Data and presents classical smoothing techniques. An empirical evaluation and comparison of combinations of smoothing and sampling techniques and their impact on the quality of the obtained distributions is presented in Sections 4 and 5. Finally, I will review related work in Section 6 before concluding the paper with a summary of the findings and a roadmap for future work. 2
Linked Open Data can be perceived as a distributed labeled graph. This view provides
the basis for formalising the underlying data model in the N-Quad [
The sampling approaches discussed in this paper can be formalised as a random selection process over a set B of base elements. This set B is derived from the quads R, but focusses on certain aspects of the data. All sampling approaches considered in this paper are then based on selecting elements in B according to a uniform probability distribution.
The set of elements selected from B then defines the criteria for selecting a subset of corresponding and relevant quads from the set R. Thus, we need two functions: (1) the function restrict : R ! B which provides a base element for a quad and (2) a function expand : B ! P(R) which provides for each base element in B the set of quads relevant to it. Sampling is then performed over the set B using a uniform distribution, i.e. the probability of selecting a specific element b 2 B is p(b) = 1 . The overall jBj sampling approach is implemented in three steps: (1) by computing the set B from R using restrict, (2) by performing a sampling on B and (3) by expanding the obtained subset of B into a reduced RDF data graph via the expand function.
There are three straight forward approaches for sampling which can easily be expressed in such a formalisation framework. None of them requires a deeper interpretation or analysis of the data or the incorporation of background knowledge. I will focus on these approaches because they are unbiased and therefore should be more suitable to provide a representative sample. (See Section 6 for related work on biased sampling techniques).
Triple (Edge) Based Sampling. The RDF data graph can be sampled using an edge based approach. This means to directly select the edges with a probability inverse proportional to the overall number of edges. The edges correspond to the triple statements of the elements in R, as each quad contains a description for the connection of two nodes. Formally, the functions restrict and expand are defined as follows. restrict : (s; p; o; c) 7! (s; p; o) expand : (s; p; o) 7! f(s; p; o; c) j 9c : (s; p; o; c) 2 Rg: (1) USU (Node) Based Sampling. The second standard approach for sampling graph data is to select a subset of the nodes. The sample of the graph is then composed on the basis of the selected nodes and their adjacent edges. In RDF this corresponds to sampling from the set of URIs used to model entities. This means that literals and blank nodes can be ignored. In the context of this paper the sampling is implemented on the basis of URIs appearing in the subject positions of triples, so called Unique Subject URIs (USU)1. Once the USUs have been selected in the random process the sample of the Linked Data graph is constructed by adding all edges which are adjacent to a URI in this set. In the formal representation this leads to the following definitions for the two functions: (3) (4) (5) (6) restrict : (s; p; o; c) 7! s expand : s 7! f(s; p; o; c) j 9p; o; c : (s; p; o; c) 2 Rg: Context Based Sampling. The last sampling paradigm I will cover in this paper is based on the context of a quad. This means sampling is performed on the set of data sources on the Linked Data cloud. Once a data source is selected for inclusion in the sample, all data provided by this source is used to estimate a distribution. Effectively, in the functions restrict and expand we only need to consider the context c provided in the quads.
restrict : (s; p; o; c) 7! c expand : c 7! f(s; p; o; c) j 9s; p; o : (s; p; o; c) 2 Rg:
Context based sampling is probably the most natural approach for sampling on the LOD cloud. It aligns very well with the paradigm of dereferencing a URI to look up information provided there. Thus, selecting a subset of all URIs for dereferencing and using all information made available under these URIs is intuitive and easy to implement in practical applications. Nevertheless, we consider the other two sampling models for the sake of completeness and for providing a comparison. 3
For any density estimation it is necessary to first define a sample space . It is the events in this space for which we attempt to determine probabilities. In the context of Linked Data the events are defined on the basis of the observed triples and typically align with a structural or content related feature of the graph and its nodes and edges.
Related work provides several considerations about different kinds of data
structures which can serve as events. For instance, a common scenario is to ask how likely
1 Theoretically, an alternative would be to consider also URIs in the object position. However,
given the structures which serve as events in the sample space this will have no practical effect
on the distributions. The reason is, that an object URI which never appears in the subject
position of a triple will not be assigned to any of these structures.
it is to observe a particular RDF class type or a particular predicate. Density
information about this basic structures can serve in RDF triple stores to estimate the size of
a result set. More complex events can be obtained when combining these basic
structures into property sets (PS, also referred to as characteristic sets) [
The notation in this paper is based on the definition of Linked Data index models [
If we have access to the full data set D, we basically have observed the full population and all frequencies. Thus, we can easily estimate the distribution using a maximum likelihood estimation (MLE). In this case the event k 2 has a probability P^MLE(k) = j D(k)j , where j D(k)j is the number of observations we have made for k
N in D and N is the overall number of all observations.
When operating on a sample S of the full data set D, the estimation of the distribution of the events becomes more difficult for several reasons. First of all, certain events k 2 might not have been observed. Thus, it is difficult to construct itself from the observations. A common approach in comprable scenarios (e.g. language modelling) is to introduce an artificial event <UNKNOWN>. This event is a representative for all events which were not foreseen in the sample space constructed over a sample S of data D.
However, using a maximum likelihood estimator would still assign a zero probability to this event, because the function S operating on the sample S would provide an empty set. Furthermore, also the estimates for the seen events will be skewed. For instance, an event k which in the full data set occurred exactly once (i.e. j D(k)j = 1) and which is contained in the random sample (i.e. also j S (k)j = 1) would be overestimated in its probability, as the size of the sample is smaller then the overall population. Thus, if M is the number of events observed in the sample, a maximum likelihood estimation P^MLE = j S(k)j = M1 is too high by a factor of MN .
M
Smoothing techniques are meant to overcome such problems. They smooth the distribution by removing probability mass from the made observations and redistributing it to unseen events. This should counterbalance both of the above mentioned problems. The smoothing techniques used in this paper are very well established but also quite simplistic. Yet, they can serve as future baseline for more sophisticated approaches. Laplace Smoothing In Laplace smoothing the number of observations for each event k is artificially increased by one (therefore it is sometimes also referred to as add-one smoothing). This gives an estimator of:
P^Laplace(k) = j S (k)j + 1
M + j j (7)
While there are certain conceptual critics towards Laplace smoothing (e.g. a tendency to overestimate rare events), it is commonly applied in practice. Lidstone Smoothing Lidstone Smoothing is a generalisation of Laplace smoothing. Instead of adding a value of one to all event counts, it involves a parameter : The general idea of the empiric evaluation provided here is to see how distributions estimated over different sample sizes, sampling approaches and smoothing techniques deviate from the distribution over a full dataset. The task addressed in this paper is the comparison of distributions. In particular, we want to find out how close a distribution obtained from a sample is to the distribution over the full data set. A common metric to compare density functions and distributions is Kullback-Leibler divergence. Kullback-Leibler divergence compares two distributions in an information theoretic context and provides an asymmetric distance between the distributions. In this section I will briefly introduce the definition of this distance function and explain the interpretation in the context of compression theory.
Kullback-Leibler divergence is based on the definition of cross entropy. Assume we have two probability distributions P1(X ) and P2(X ). In the setting of this paper, P1 would correspond to the true distribution over the full data while P2 is the distribution estimated over a sample. Then the cross entropy is defined as:
H (P1; P2) =
X P1(X = k) log(P2(X = k)) (9) k2K
In the context of compression theory, cross entropy can be interpreted as the
average number of bits needed to encode events following the distribution P1 based on an
optimal prefix-free code [
DKL(P1; P2) = H (P1; P2)
H (P1) (10)
Therefore, if two distributions are equivalent, they have a Kullback-Leibler
divergence of zero. This is a desirable feature for our evaluation as it renders the comparison
of distributions over samples of data independent from the different levels of the entropy
observed for different sample spaces defined by different observable structures.
We use data from the Dynamic Linked Data Observatory (DyLDO) data set [
Starting from this full data set I generated samples of decreasing size. The sample size was defined by a sampling rate. This rate covered values from 90% down to 10% in steps of 10% and an additional very small sample of 5%. To avoid unfortunate random configurations of the samples I repeated the process for each sample size and sampling method ten times. Thus, in total I created 300 samples (three sampling techniques, ten sample sizes, ten iterations), which were all taken independently from each other (in the probabilistic sense). Table 1 shows the average size (in number of triples) of the samples for each sampling method and sampling rate. The numbers illustrate that none of the sampling techniques exhibits a systematic tendency to generate too large or too small samples. This is visible in particular also in Figure 1 which depicts the same numbers as a plot. The lines for each sampling technique are essentially the same.
For each sample I constructed index structures2 to obtain frequency counts and estimated distributions using the different smoothing techniques. For Lidstone smoothing the parameter was set to = 0:5, 0:1, and 0:01. For each such configuration of sam2 The implementation of the index structures as well as sampling and smoothing techniques is available under an open source license at https://github.com/gottron/ lod-index-models.
Sampling Ratio
Triple
USU pling technique and smoothing approach I then computed the distribution for each of the samples and compared it via Kullback-Leibler divergence to a maximum likelihood estimation of the distribution over the full dataset. The obtained values were used to plot a curve of how the divergence evolves on the basis of the sampling rate. This process is also illustrated in Figure 2. The plots presented in the subsequent section actually show the average values for Kullback-Leibler obtained over the ten samples generated for each combination of sampling technique and sampling rate. 5
Let us first compare the different sampling techniques. In Figure 3 we can observe how Kullback-Leibler divergence increases when reducing the size of the sample. Each plot corresponds to a different structure used as events for the sample space (RDF types, predicates, type sets, predicate sets and extended characteristic sets). The different lines in the plot demonstrate the value of the Kullback-Leibler divergence for the three different sampling strategies based on triples, USUs and context. All distributions for the settings in Figure 3 were smoothed using the Laplace approach.
The plots illustrate nicely how the different sampling strategies affect the quality of the density estimations. Sampling based on USUs shows a very low Kullback-Leibler divergence even for high sampling rates. This behaviour is consistent across all types of structures considered as events. However, we can also observe that the quality of distributions estimated for simpler structures, e.g. the RDF types or predicates, is better than for the more complex structures, e.g. ECS. This is plausible as the definition of an extended characteristic set involves more triple statements, namely each RDF type assignment and all used predicate URIs. Thus, sampling is more likely to cause the loss of some of the information required to reliable obtain the actual structure.
This is also the reason why triple based sampling demonstrates the worst quality on this type of structures. When using triple based sampling for a subsequent estimation 5% 10% 20% 30% 90%
Full (100%) Index construction / Estimation of distributions 10% 20% 30% 90% 100% of the distribution of PS and ECS structures Kullback-Leibler divergence is increasing very fast, even for high sampling rates of around 80%. Obviously, sampling just a fraction of the predicates leads to wrong structures and to strong deviations in the overall distribution. For type sets, interestingly, this effect is far less strong. One explanation can be that there are less type set combinations than property sets combinations in the analysed data set (25,727 TS vs. 35,985 PS). Thus, there are far less combinations which can be confused and distort the distribution. Furthermore, entities are typically annotated with only a few RDF types (if at all). Thus even after sampling, the odds are quite high to still observe a quite representative set of RDF types and their combinations. For the distributions over structures which are based on single triple statements, i.e. the RDF types and predicates, triple based sampling is behaving extremely well and comparable to or even slightly better than USU based sampling.
When employing sampling based on the context, the quality of estimated distribution is never the best. However, on the more complex structures it behaves better than the triple based sampling. And for sampling rates going down to 50% the Kullback-Leibler divergence also is not too high for all structures. An explanation for the sub-optimal behaviour is that context based sampling is prone to a domain bias. Based on the actual contexts sampled certain “regions” of the Linked Data cloud might be covered better than others. This might also explain that the plots of Kullback-Leibler divergence over context samples show more variance and look more rugged than the plots for the other sampling techniques.
3 e cne 2.5 g irveD 2 r leb 1.5 i -kceL 1 llbau 0.5 K 0 0
3 e cne 2.5 g irveD 2 r leb 1.5 i -ckeL 1 llbau 0.5 K 0 0 0.2 0.2 1 1
In Figure 4 we see the impact of different smoothing techniques on the KullbackLeibler divergence. The figures do not show all combinations, but illustrate some of the corner cases as well as realistic settings. Figure 4(a), for instance, shows how the distributions estimated over predicates behave when using a context based sampling. The choice of the smoothing model shows very little effect on the quality of the estimated distribution. Also in Figure 4(b), showing the divergence for triple based sampling, the lines for the different smoothing techniques essentially match. Note, the different reso0.4 0.6 0.8 Sampling Ratio
Lidstone 0.1
Lidstone 0.01 (a) Predicates, context sampling 0 0.2 0.4 0.6 0.8 Sampling Ratio
Lidstone 0.1
Lidstone 0.01 (c) ECS, context sampling 1 1 0.4 0.6 0.8 Sampling Ratio
Lidstone 0.1
Lidstone 0.01 (b) Predicates, triple sampling 0 0.2 0.4 0.6 0.8 Sampling Ratio
Lidstone 0.1
Lidstone 0.01 (d) ECS, USU sampling 1 1 lution on the y-axis. As stated above, the quality for predicate estimates is by far better when using triple based sampling. However, with the more detailed resolution in Figure 4(b), we can identify a slight advantage for Lidstone smoothing with a small value for parameter .
Looking at the estimates for the more challenging ECS structures, instead we observe a different behaviour. In Figure 4(c) we see again context based sampling. However, in this setting, Laplace smoothing shows the best performance. In the better performing USU sampling, instead the order is reversed. Here it is again Lidstone smoothing with a small setting for which provides the lowest deviation when estimating the distribution of data items over extended characteristic sets.
While in the previous examples we observed relatively small difference in quality between the individual smoothing techniques, we can see some examples for a stronger impact in Figure 5. In both shown plots we observe strong changes in KullbackLeibler divergence. The most extreme case certainly is Figure 5(b), where the divergence reaches values of up to 3 at small sampling rates. 9 cne 8 rge 7 ive 6 reD 5 l ib 4 e -kL 3 ca 2 llub 1
K 0 0 0.2 0.4 0.6 0.8 Sampling Ratio
Lidstone 0.1
Lidstone 0.01 (a) TS, triple sampling 1 0 0.2
1
In the database world the estimation of densities has a long tradition in the context of
query result set size estimation. Mannino et al. [
For sampling on RDF data there is relatively little work, so far. Sundra et al. [
Estimates of distributions over RDF Data find their application in several scenarios.
Obtained from locally stored data sets they are used for the purpose of query
optimisation to estimate the result set size for query fragments [
In this paper I addressed the task of sampling the LOD graph for the purpose of
estimating data distributions. I looked at the effects of standard sampling and
smoothing techniques on the quality of the estimates of distributions. In an empirical
evaluation it could be observed that an USU based sampling over the modelled entities
provides the best results for obtaining reliable distributions. This could motivate data
providers to describe their entire data set with a small excerpt based on this
sampling technique. The examples could easily be incorporated, for instance, in a VoID
description [
While the paper at hand gives an overview of how existing standard techniques
perform, it can only provide first insights and a baseline for further investigations. Thus,
in future work I will investigate alternative smoothing techniques. A very promising
idea seems to adopt generalised approaches from the context of language modelling [
Acknowledgements The research leading to these results has received funding from the European Community’s Seventh Framework Programme (FP7/2007-2013), REVEAL (Grant agree number 610928).