Datasets in the LOD cloud are far from being static in their nature and how they are exposed. As resources are added and new links are set, applications consuming the data should be able to deal with these changes. In this paper we investigate how LOD datasets change and what sensible measures there are to accommodate dataset dynamics. We compare our findings with traditional, document-centric studies concerning the “freshness” of the document collections and propose metrics for LOD datasets.
The Linked Open Data (LOD) movement has gained remarkable momentum over the past years. At the time of writing, well over one hundred datasets – including UK governmental data, the New York Times dataset, and LinkedGeoData – have been published, providing several billion RDF triples interlinked by hundreds of millions of RDF links. Some datasets, such as DBpedia, have been available from the very beginning of the LOD movement and regularly undergo changes on both the instance level and the schema level. New resources are added and old resources are removed; new links are set to other datasets, and old links are removed as the target has vanished. We should hence assume that datasets in the LOD cloud are dynamic in their very nature. Dataset dynamics is a term we recently coined [1], essentially addressing content and interlinking changes in Linked Data sources.
Our main contributions herein are: (i) define dataset
dynamics characteristics and how to measure them, and (ii)
compare the dataset dynamics of the LOD cloud to the
traditional Web (Web of HTML Documents). The motivating
use-case for our study of dataset dynamics is to gain
insights into – and hopefully improve – concurrent work on an
efficient system for performing live queries over the Linked
Open Data Web [
We begin in Section 2 by reviewing existing work, and continue in Section 3 by discussing and contrasting document vs. entity centric perspectives concerning dynamics. Thereafter, in Section 4 we present the background of our analysis, in Section 5 we describe our methodology for analysing dataset dynamics, and in Section 6 we discuss the results of our analysis. Finally, in Section 7, we conclude and render future work. 2.
As motivated above, the study of changes in documents
and data sets is very relevant for a broad range of application
domains. Earlier work discussed analysis of the dynamics of
the Web circa. 2008, leveraging their findings for
optimisation of re-indexing techniques [
With respect to the Semantic Web, some research
regarding dynamics has been conducted with respect to analysing
the evolution of ontologies in the life science community [
However – and to the best of our knowledge – we are not aware of any published studies more generally regarding the change frequency of resources on the Linked Open Data Web, and thus deem the work herein to be novel. 3.
There are various aspects of dataset dynamics which must be considered in order to achieve a comprehensive overview of how Linked Open Data changes and evolves on the Web. Firstly, the change frequency of data on the Web can vary significantly across datasets, from rather static sources – such as archives – to high-frequently changing sources – for example in the micro-blogging domain. Also, the change volume can range from small-scale updates – in our case, updates involving a low number of triples – to bulk updates, which potentially affect many resources. One must also pay attention to the perspective one takes on resources: that is, whether we are interested in local changes of particular datasets, or are interested in global changes with respect to what is said about a URI in all accessible linked datasets.
Before we continue, however, we must first provide some
preliminaries. Firstly, our notion of a ‘document’ refers to
an atomic Web ‘container’ in which Linked Data is typically
exposed: these include RDF/XML, (X)HTML+RDFa
documents, etc. Secondly, we often refer to an ‘entity’ by which
we intuitively mean anything identified by a URI in Linked
Data, including classes, properties, and the “real-world
artefacts” described.1 Following from both, we can now
distinguish the following perspectives in dataset dynamics:
1. A document-centric perspective, which focuses on
datasets and is motivated by the “traditional” Web as well
as the REST community [
In fact, the global entity perspective may be infeasible to monitor as arbitrary new sources can publish data about any entities. For this reason – and despite formally discussing 2b herein – note that in the present work we will focus on the analysis of 1 and 2a, and leave approximative techniques for analysis of 2b as part of our future research (discussed in Section 7).
Despite the two distinct perspectives, both are somehow
related: there is naturally a relation between entities and
their appearances in different containers. Along these lines,
Figure 1 depicts a typical distribution of entities per
document in the LOD cloud. As we have already shown
elsewhere [
In order to formalise what we mean by these different
perspectives, let R = {r1, ..., rn} be the set of all resources
as of the Architecture of the World Wide Web [
100 1000 number of entities per document 10000 various entities; thus, we denote the set of entities mentioned in document d as E(d) ⊆ E and likewise the set of all documents mentioning e as D(e) ⊆ D. Further, let ver(d, t) be the state of document d at time-point t – i.e., the RDF graph served by d at time t. It is clear, that different use cases require specific state functions ver(d, t) and equality measures; e.g. a state function could be the hash value of the RDF graph, a set of RDF statements or the set of inferable new statements.
Then, the document change function of document d from time t to t0 (where t < t0) is defined as follows:
Definition 1. Document Change Function
Cd(t, t0) = 0 1 if ver(d, t) = ver(d, t0) otherwise Likewise, we define the entity-per-document change function as follows:
Definition 2. Entity-per-document Change Function Cde(t, t0) = 0 1 if ver(d, t) ∩ e = ver(d, t0) ∩ e otherwise where by G∩u we denote all triples in graph G mentioning u. Finally, the entity change function can be defined as follows: Definition 3. Entity Change Function
Ce(t, t0) = max∀d∈D(e)(Cd(t, t0))
Please note that we pursue a purely ‘syntactic’ notion of change, and do not consider more advanced notions relating to ‘semantic’ change: for example, we would consider a change in a datatype literal if the syntax of that literal changes even though the semantic interpretation does not – this change would then propagate to the respective entity/document despite no real change on the semantic level. Further, we do not consider any forms of reasoning in the changes – e.g., we do not propagate changes in a class definition as changes to it’s member entities. We leave further discussion and related analysis of ’semantic vs. syntactic change’ for future work.
It may also be interesting to consider more closely the
relationship between documents and the entities they contain,
examining separately the change function of entities which
are considered ‘local’ with respect to the document they
appear in. To this end, we introduce the term local entity,
meaning an entity in a document whose pay-level domain
(PLD) is the same as the document’s PLD: here, a PLD is
defined as any domain that requires payment at a
[top-leveldomain] (TLD) or country-code TLD registrar [
P LD(http : //www.deri.ie/) = deri.ie We can now define a local entity as follows:
Definition 4. Local Entity We define the set of local entities Elocal(d) of document d as
Elocal(d) = {e ∈ E(d) | P LD(e) = P LD(d)}
Definition 4 is closely related to a similar notion defined
in [
So far, we have focused on identifying and formalising
different notions of change – particularly change functions
– as a foundational aspect of dataset dynamics. We now
discuss how such changes can be detected; one can group
change detection mechanisms as follows:
• HTTP-metadata monitoring: analysis of HTTP
response headers – including datestamp and ETag [
The Table 1 summarises aspects of the the
aforementioned change detection mechanisms. The aspects –
motivated by [
Both content and HTTP metadata monitoring
mechanisms are well studied and discussion about those is available
elsewhere (cf. [
Notification
+
+
high
high
yes
no
± [
± [
To the best of our knowledge, this is the first study
regarding the dynamics of documents and entities of the Linked
Open Data Web. Hence, the methodologies used in our
evaluation are inspired by legacy related work for Web
documents. Specifically, we applied similar evaluation methods
– and indeed try to answer similar questions – as presented
in [
To gain first insights about the dynamics of resources of
the Linked Open Data Web we analyse 24 data dumps
collected by weekly snapshots of the 7 hop neighborhood of
Tim Berners-Lee’s FOAF file5. The weekly snapshots were
collected using the MultiCrawler framework [
5. applying a per-domain limit for the URIs (5000 URIs per PLD).
Please note that steps 4) and 5) were done for politeness
reasons to prevent too many parallel HTTP requests to one
server: these steps introduce a non-deterministic element
into our crawl and thus, we did not monitor a fixed list of
URIs every week. Indeed, this passive monitoring makes
change frequency analysis more challenging [
The data collection was performed over 24 weeks starting from the 2nd of November 2008 and contains 550K RDF/XML documents with a total of 3.3M unique subjects (∼6 entities appearing in the subject position per source) with 2.8M locally defined entities per our definition 4. 5.3
The change detection of a document Cd(t, t‘) or entity
Cde(t, t‘) between two snapshots t, t‘ is a trivial task as long as
the statements of the resource do not contain blank nodes [
In this subsection, we describe in detail the evaluation we performed on the data set.
Document-centric evaluation. Firstly – and as a baseline – we performed a document-centric evaluation which allows us to compare our results with earlier studies about HTML documents. For this study, we compute the changes of a document as defined in Definition 1.
Entity-centric evaluation. Secondly, we studied the change frequency of entities from an entity-per-document perspective as defined in Definition 2. In fact, more accurately we analysed the change frequency from a local-entity-perdocument perspective – a notion which follows intuitively from Definitions 2 and 4: to detect a change in an entity Celocal (t, t‘), we compare only the statements which 1) are d contained in documents whose URIs matches on the PLD level with the entity URI and 2) in which the entity URI appears in the statement. Thus, we consider only the changes from documents in the locality of the entity as defined in Definition 4. 5.5
Finally, for the purposes of comparison, we use an
established model for changes of Web documents. Previously
published studies [
k! P [N(t + τ ) − N(t) = k] = exp(−λτ ) for k = 1, 2... (1) 6.
In this section we present several early findings about the change frequency of resources on the Linked Data Web.
Firstly, we examine the usage of Etag and Last-Modified
HTTP header fields, followed by an analysis of the various
dynamic aspects which are aligned to the studies of the
traditional Web in [
Usage of Etag and Last-Modified
One way to detect changes is to use the information contained in HTTP response headers as discussed in Table 1. The HTTP protocol offers two header fields to indicate a change of a document, viz: the Etag and Last-Modified fields. Using such methods of change detection is more economical in that it avoids the need for content sniffing.
We verified the usage (or lack thereof) of these two fields for all the documents in our corpus; Table 2 summarises the findings:
only Etag only Last-Modified Both None
7.12% 8.18% 16.75% 67.95%
Similarly to studies about the usage of these two fields
for HTML documents [
We move now to analysis involving the content of data in
our corpus. Firstly, we are interested in characterising the
distribution of the number of accesses (i.e., appearances)
and the lifespan (i.e., the time interval between the first
and last appearance) of documents and entities respectively.
This is a slightly different computation from [
From this figure, we can also conclude that only a fraction of the documents appeared frequently in the different snapshots – considering the importance of having as much information as possible to apply and verify our change frequency model (Section 5.5) – and thus to gain a good overview about their dynamics – going forward, we will give special consideration to the subset of our corpus derived from documents that appear in at least 20 weekly snapshots and ignore missing observations when considering changes. Again, this is necessitated by the non-deterministic factor in our incidentally crawled snapshots.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 number of weeks
Next, we will analyse the average change frequency of a resource. For the purposes of this analysis, we only consider the subset of the corpus which features resources that appear in more than 20 snapshots. Let us assume a document d changed 12 times during our monitoring interval of 24 weeks. In this case we can estimate the average change frequency of d to be 24 weeks/12 = 2 weeks. Following this example, the results for average change frequency of documents and 1000000 1t00000 n u o c 10000 1000 documents (accesses) documents (lifespan) entities (accesses) entities (lifespan) 80% 70% 60% 50% n o it rca40% f 30% 20% 10% 1000000 100000 iitts10000 e n foe1000 r e b um 100 n 10 1 entities are summarised in Figure 3. The left side of the diagram shows the percentage of all resources that were not observed to change (static resources). The right side of the diagram shows the percentage of non-static resources that were observed to have an average change frequency within the given interval. An interesting finding is that 62% of the total documents did not change at all, along with 68% of the entities. Further, we see that the fraction of documents is increasing with bigger change intervals, whereas for entities it is quite the opposite: by inspecting the data closer, we figured out that 51% of the entities with a change frequency of less than 1 week appear in more than one ‘local’ document. Thus, for example, one document may change the description of many local entities: along these lines, Figure 4 shows the distribution of the number of frequency of entities appearing in a given number of documents, where again, we can observe a power law distribution.
62.12%
68.88% static 52%
24% 23% 9% 9%
10% <1 week
≤>11wmeoenkth ≤>13mmoonntthh average change frequency 59%
Continuing, we now study how quickly and what fraction of the documents and entities changes over time. Along these lines, we count how many documents – and respectively entities – changed after a certain time period. Figure 5 presents the cumulative change function for documents (circles) and entities (squares). The graph cumulatively shows how many documents and entities had changed after X weeks. The plot contains the cumulative change function for all resources (appearing at least once), and for resources that appeared in at least 20 snapshots. Again, the plot correlates with Figure 3 in that for the subset of the corpus with more than 20 observations, we can also see a large amount of entities changing after the first week, with a more gradual increase in observed document changes. An interesting observation is that the entities with more than 20 observations show a higher propensity to change; one could assume that such entities are better linked (and thus appear more often in our crawl) and so are reused in more documents (cf. Figure 4).
documents documents (#occ > 20 weeks) entities entities (#occ > 20 weeks) 30 % n ito20 % c a fr 10 % 0 % 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 number of weeks
Next, we analyse whether we can apply the Poisson model presented in Section 5.5 to the changes of documents and entities detected in our analysis. Therefore, we must compute the average change rate λ for each document d and entity e. We group the documents and entities with the same change rate and plot their distribution of successive change intervals; e.g., a document which changed in week 2 and 6 has a successive change interval of 4. If the changes can be modeled as a Poisson process, the resulting graph should be distributed exponentially.
For illustration, we selectively present the graph for documents with an average change frequency of 4 weeks (Figure 6) and the graph for entities with an average change frequency of 4 weeks (Figure 7). We performed a Poisson regression ( log-linear regression) and use the maximum likelihood method to estimate the parameters. The predicated poisson process is plotted in the graphs as the line and describes the observed data quite well, despite some small variations. Similar effects are observed for around half of the other plots. However, we also spotted several graphs for documents and entities in which the Poisson model does not well describe the observed data points: The main reason for this observation is that there are not enough available sample points. As a conclusion of the findings: we currently cannot accept or reject the described change model with statistical significancy. Further studies with more data samples are required.
We found that in 90% of all documents less than 10% of the entities changed, as depicted in Figure 8, which shows the distribution of the average fraction of entities that changed per document. It is hence safe to assume that – in the context of Linked Data – the finer-grained entity-centric perspective for changes is superior, compared to the more traditional document-centric point of view.
Drawing towards a conclusion to our analysis, we now discuss the observed changes for the documents over time. Therefore, we defined the following three main change categories: • Update (U) – that is, between two snapshots of a document, the entities described were the same but the information about the entities changed: new statements were added and/or removed; • Add (A) – that is, between two snapshots of a document, new entities were added; • Del (D) – that is, between two snapshots of a document, entities were deleted; • Combination of the three categories mentioned above:
UA, UD, AD; UAD.
Table 3 lists the fraction of documents which encountered such a change (or combination thereof) for each of the seven categories. We can see that 76% of the documents have only entity updates as changes, whereas in 9.46% of the documents new entities were added.
U A D
We motivated this work by highlighting the importance of a fundamental understanding of dataset dynamics with respect to Linked Open Data sources; we further claim that such knowledge can be leveraged to optimise existing systems and algorithms, such as making incremental index updates techniques more efficient. Further, we discussed in detail the differences between document-centric and entitycentric dynamics together with possible approaches for change detection: content-monitoring, HTTP header monitoring, and active notifications.
The findings we gained from weekly snapshots of the neighborhood graph of Tim Berners-Lee FOAF file are the following: • less than 35% of the monitored documents contained Etag and Last-Modified HTTP header fields in the response; • a surprisingly small amount (∼ 35%) of the monitored resources changed over the time interval of 24 weeks; • half of the documents that changed had a change frequency of more than 3 months – in contrary, on a entity-centric level, half of the entities had a change frequency of less than a week applying our definition of local entities (based on PLD correspondences between document and entity); • comparing our results to previous published studies we cannot verify that the change frequency of the documents and entities follow entirely the change model of a Poisson process.
We should perhaps look at these early findings with a critical eye in that we did not actively monitor a fixed set of sources. This work is very much an early attempt in this field, and needs further exploration and research to fully understand and exploit the change frequency of resources in the Linked Data Web. 7.1
Large scale experiment To verify our early findings and
derive statistical significant results, we plan to expend and
run our evaluation for a larger dataset which is monitored
over a longer time period. Further, we plan to study in more
detail the dynamics on a entity-centric level; e.g. studying
the dynamics of only authoritative entities as defined in [
Active monitoring. A major drawback of the current study is the monitoring method used for our data set. To overcome the problem of an incomplete change history, we will actively survey a selected set of documents over a long time period, thus creating a tailored corpus for our analysis. In addition to active monitoring, we plan to study how we can dynamically adapt the monitoring interval based on the estimated change frequency of a resource.
Fine-grained analysis of changes on a entity-centric level
Finally, the findings of this work will be integrated into an
existing system which aims to execute live queries over the
LOD Web, which uses efficient data summary approaches [
Our work has partly been supported by the European Commission under Grant No. SFI/08/CE/I1380 (Lion-2), and under Grant No. 231335, FP7/ICT- 2007.4.4 iMP project. Further, this work has greatly benefited from the feedback of Bernhard Haslhofer and Nico Popitsch as well as from discussions with Andreas Harth. 9. REFERENCES [1] Dataset dynamics (esw wiki).
http://esw.w3.org/topic/DatasetDynamics.