Existing Web archives aim to capture and preserve the changes of documents on the Web and provide data corpora of high value which are used in various areas (e.g. to optimise algorithms or to study the Zeitgeist of a generation). So far, the Web archives concentrate their e orts to capture the large Web of documents with periodic snapshot crawls. Little focus is drawn to preserve the continuously growing Web of Data and actually keeping track of the real frequency of changes. In this work we present our e orts to capture and archive the changes on the Web of Data. We describe our infrastructure and focus on evaluating strategies to accurately capture the changes of data and to also estimate the crawl time for a given set of URLs with the aim to optimally schedule the revising of URLs with limited resources.
DBPedia project, which converts Wikipedia articles to Linked Data and
releases infrequent dumps of their data [
In this work, we propose and envision a distributed infrastructure to capture and archive the evolving Web of Data. While we provide some initial starting points to this infrastructure, which we have already implemented and started to deploy, we argue that this infrastructure should be joint e ort due to the underlying complexity and the resource demands which can be solved by distributing the crawling and storage tasks. In the remainder of this work we highlight the general envisioned infrastructure in Section 2 and presents our e orts for a exible and extensible archiver component in Section 3. We introduce various strategies and discuss our results to accurately capture the changes of documents in Section 4 and we introduce and evaluate a heuristic to estimate the crawl time for a given set of URLs in Section 5. Eventually, we conclude and present future direction in Section 6. 2
The necessary infrastructure to capture and preserve the data on the
Web of Data should be similar to a distributed Web crawler
infrastructure [
ARCHIVE ARCHIVER
ARCHIVER
ARCHIVER
should indicate that each unit can exchange basic information such as,
the current capacity or which URLs are currently in the system. These
information should then be used to decide to which units new URLs should
be added and where to get the versions for a particular URL. We identify
the following requirements for our envisioned infrastructure:
{ Distributed, the infrastructure needs to be distributed since no
single party can provide the necessary resources to capture the changes
of the Web of Data. Clearly, a company such as Google or maybe even
the Web archive has the necessary infrastructure, but we do not see in
the near future any e orts to capture the changes on the Web of data.
As such, preserving the Web of Data can be achieved if several parties
join e orts by archiving a manageable subset of documents based on
the available resource. One further advantage of the distributed
architecture is that the URLs can be geographically distributed which
can improve the throughput [
We started to develop the archiver component of our envisioned infrastructure and discuss the general architecture depicted in Figure 2. Our archiver, called datamonitor, consist of the following loosely coupled components: { The meta data store uses currently a Postgres database and stores all vital information such as crawl logs, scheduling information and Data Monitor Framework URI type
scheduler
cron
data
YYYY/MM/DD/HH/domain
downloader
politeness queue meta
content
crawl
schedule
crawl
metadata
links
cron
also aggregated statistics. For instance, one crawl log entry contains
information about the HTTP response header, the download time and
a change state indication if the document changed compared to the
last download based on a content checksum. Another table in the
meta data store contains information about the next crawl time and
the current crawl frequencies for each URI.
{ The scheduler component periodically access the meta data store
and retrieves the URLs for the next crawl which are then processed
by the downloader component
{ The downloader component retrieves the content of a list of
supplied URLs and archives the downloaded data and collected meta
data. The framework is a multi-threaded Web crawler which respects
the robots.txt protocol3 and crawl delays and uses a politeness queue
to avoid overloading the servers with too many requests [
We decided that the downloader and scheduler component should run in regular intervals to make the framework more robust rather than an online system in which the downloader component would listen if new URIs should be crawled. However, this online design would require solutions to periodically persist the current state of the system to be able to recover the state in case of unexpected system crashes, e.g., due to memory exceptions or short term shutdowns. In our current design we
can assure that the di erent components run independently and in xed intervals and that a problem in one crawl does not a ect the next crawls. We decided to start our scheduler and crawler every hour. As such, we should ideally schedule the crawl time of the URLs in such a way that each crawl can be completed in less than one hour to avoid an overlap of crawls which can cause a resource problem.
Another feature of our architecture is that the components are exible enough to adapt to various scenarios. With the current architecture it is easy to extend our checksum based content change detection and integrate for example le format tailored algorithms or graph isomorphism check to determine more accurately changes in RDF les. 4
One of the core algorithms in this framework is the adaptive scheduler
which determines the next crawl time for URLs based on the content
change information and current download frequencies (see Figure 2). The
literature lists several approaches to reschedule crawls for HTML data
(e.g., [
Next, we introduce various strategies which we evaluate in terms of how accurately they capture the changes of documents. Figure 3 depicts different strategies and how they capture or miss changes of a document. The top row shows the actual time points for the changes of a document over 20 time units with an average change rate of = 0:5 changes per time unit (10 changes in 20 time units). Below are two di erent strategies; the middle one accesses the document with a change frequency of and the bottom one simulates a simple adaptive strategy which increases the download frequency if we observe more changes and decreases the frequency if we observe less changes. On the side we show the numbers of changes captures and downloads performed. We can see that the middle strategy is overall better since the bottom strategy performs three more downloads to captures the same amount of changes.
real avg adaptive 0 4 x 8 x x
x 12 16 changes lookups
Next, we present our strategies to decide if to increase or decrease the crawl frequency for a document based on the history of observed changes. The crawl frequency for all strategy is xed between a minimum and maximum value. fix and dyn: Dynamic crawl frequency adaptation based on a xed number of snapshots This strategy determines if the crawl frequency should be changed based on a xed number of last observed snapshots. First we determine how many observed snapshots with the same crawl frequency will be considered. We use two di erent methods: fix uses the last two snapshots dyn determines the number of snapshots based on the current crawl frequency. We use one snapshot if the frequency is higher than 2 month, 2 snapshots if it is higher than 1 month, 3 snapshots if higher than 1 weeks and 4 snapshots if higher than 1 day.
Next, we increase the frequency if the document changed in all snapshots and decrease the crawl frequency if the document did not change, otherwise we do not adapt the frequency. The actual frequency change depends again on the current frequency: We increase the frequency by a factor of 1.5 in case the old crawl frequency is higher than 1 month and use a factor of 2 otherwise. Similarly, we decrease the frequency by a factor of 1.5 in case the current crawl frequency is lower than 1 month, otherwise we decrease by a factor of 2. window: Dynamic crawl frequency adaptation based on a window of snapshots: This strategy is similar to the previous one. However in contrast, we compute the ratio of detected changes divided by number of snapshots. We consider either the last ten snapshots or half of the available snapshots. We use the following formula to compute the new frequency based on the computed ratio: If the ratio r is higher than 0.9 we increase the frequency by dividing the current frequency by a factor of 3, if r > 0:75 by a factor of 2 and if r > 0:6 b a factor of 1.5. Similarly, we decrease the frequency by multiplying the current frequency by a factor of 3 if r < 0:1, by a factor of 2 if r < 0:25 and by a factor of 1.5 if r < 0:4. The general idea behind this is that the higher the ratio the more we increase the frequency and the lower the ratio the more we decrease the frequency. state-1 and state-2 Dynamic crawl frequency adaptation based on state change probabilities In this strategy we apply the markov chains approach to determine the likelihood to observe a change in the next download considering the past observed change. We separately maintain the knowledge about the sequence of observed states for each crawl frequency. The use this information to compute the probability that the document changes in the next download based on this state-change knowledge base. Currently, we have two variations of the markov models: state-1 considers only the last state of a document to compute the likelihood of the next state. Table 1 shows an example knowledge base in which we store how often two change states appeared ('0' indicates no change and '1' indicates a document change). For instance, the value (n = 1, n 1 = 1) indicates that we observed 10 times that the document changes in a row and that we observed 40 times a change after a non-change(n = 1, n 1 = 0). We use this information to determine how likely it is that the document changes in the next download: For instance considering our example table: P (1j0) = 4500 = 0:8 state-2 considers the last two change states of a document to compute the likelihood of the next change state. In contrast to state-1, we store the information about the occurrences of the last two change states.
Eventually, we compute the new crawl frequency based on the computed likelihood to observe a change in the next crawl. We use the same frequency in/decrease factors as in the window strategy. gold Gold standard We also use a reference strategy which downloads the documents according to their overall change frequency which we assume is know in advance. To do so, we calculated the average change frequency for each page based on the actual Wikipedia revision history. week In addition, we simulate a crawl with a xed frequency of 1 week. 4.2
We evaluate the performs of our strategy with two measures from Information Retrieval area, namely the recall and precision. In an ideal case we would capture all changes of a document exactly shortly after they happen. In this ideal case, we would capture all changes and would only require the same number of downloads as changes. As such, we compute the recall of a strategy by counting the changes we observed and divide it by the real number of changes that actually happened. The precision is de ned as the number of observed changes divided by the number of downloads.
Data We use the revision history of Wikipedia changes as our corpus to test various strategies for adapting the re-crawl frequency for documents to capture and preserve their changes. The reason for this is the already mentioned observation that the change rates of Wikipedia article do not follow any particular distribution and that the revision history of the articles span over several years, providing us a large enough time span to test our strategies.
To collect our evaluation corpus, we performed the following steps: 1) we randomly selected Wikipedia articles and gathered their revision history using the provided API.4 Next, we lter out articles for which the revision history is shorter than 3 years and discard revisions which are declared as minor revisions. Eventually, we grouped the articles based on their average change rate which is computed by the number of revisions divided by the history time. Eventually, we use the revision histories of 2660 articles with varying average change frequencies and that provide a history of more than 3 years.. Table 2 provides the detailed overview about the distribution of documents according to their change frequencies. We aimed to select 300 documents for the various subsets. 4.3
We simulated a crawl for each document over 3 years with the various strategies and present the aggregated recall and precision values for the
di erent set of documents (see Table 2) and for all 2660 documents. We xed the minimum crawl time to 1 day and the maximum to 6 month.
Figure 4 shows how the various strategies perform across all documents. In general, we observe that all strategy trade recall for precision or vice versa. We also see that the strategies perform overall very similar and only the week and window strategy show two extreme behaviours. The week strategy performs overall the best in terms of recall and worst in terms of precision. This is to be expected since 92% of our documents have an average change frequency of more than 1 week and it is very likely that we capture most of the changes, however the strategy also requires a signi cant number of unnecessary lookups. Next, we can see that the probabilistic strategies state-1 state-2 are the second best in terms of recall and second worst in terms of precision. The xed snapshot strategies fix and dyn follow closely the strategies with the markov models. The window strategy in contrast trades recall for a high precision. An interesting observation is also that our strategies seems to get better over time in terms of precision which is one of the desired e ect and indicates that the adaptive rescheduling can improve the overall performance.
Next, we discuss the results for selected sets of documents. Figure 5 shows the precision and recall for documents with an average change frequency between 2 days and 1 week. We see that only the fix and window strategy show extreme behaviours. The probabilistic strategies (state-*) are close to the performance of the actual change frequency (gold), indicating that with our current parameters we are able to predict with a good accuracy the actual change frequency for documents.
Figure 6 shows the results for the documents with between 4 and 6 month. Surprisingly, the window strategy performs very similar to the actual change frequency, while the other strategies achieve a high recall but with low precision. Again, we can observe that the probabilistic based heuristics perform better in terms of recall and worse in terms of precision as the xed snapshots strategies.
We observe similar patterns for the other sets of documents and have to unfortunately omit the plots due to space limitations. 4.4
Overall, we can conclude that so far the window strategy should not be considered due to its very low recall values. The main di erence between the xed snapshot and probabilistic strategies is that the former have a smaller trade o between recall and precision. However, the strategies using the markov model perform very similar for all subsets while the other strategies can have di erent trade-o s for di erent subsets. As such, we will in future work focus on studying in more detail rescheduling algorithms based on markov models and also will use them for now in our architecture. 5
The second experiment evaluates a heuristic to estimate the crawl time given a set of URLs and the information gathered from previous crawls. The problem we address is to compute the crawl time for a given number of URLs using a maximum number of threads. We rst group the set of URLs by their domain and estimate the crawl time and number of threads we can use to crawl each domain based on the crawl delay. We use the average download time for a document for a given domain and the general crawl-delay per domain. This allows us to estimate crawl times for URLs which are not yet in our system, however, we also need to assign default times and delays which are currently set to 1sec for the domain-crawl delay and to 2 secs for the average crawl time.
We compute the number of maximum threads to crawl the URLs for one domain by dividing the average crawl time c by the domaindelay d (threads = dt ). Figure 7 shows an example of a crawl process for 6 documents with a given domain-delay (on the top axis) and an average document crawl time which is more than three times the delay. The resulting number of threads in this scenario is 3 and the process would be as follows: Thread 1 (t1) starts to crawl doc1 and after the delay time another thread can crawl the next document (t2 and doc2), and so on. Once we have the number of threads we compute the total
time
crawl time as follows crawltime = tdhorcesadts + d (threads 1) We map
the estimation of the total crawl size in this multi-threaded scenario to
a bin packing problem and apply a rst- t bin-packing algorithms [
We performed rst experiments which our crawl time estimation algorithms based on 1388 crawls with crawl times ranging from less than 30 minutes to over 2 hours. We evaluate by how much we over or underestimated the actual crawl time. Table 3 shows the average under or overestimation fraction for the various crawls grouped by their frequency. We can see that our current heuristic tends to overestimate the crawls by a large factor. In contrast, the underestimation is very small considering the overall crawl times. For instance, we underestimate the crawls which 5 The maximum number of threads depends on the available hardware take around 60 mins by around 10 minutes. Overall, the results are not entirely satisfying and we will investigate improved algorithms in future work. However, the results are already encouraging and actual usable for the overall scheduling of URLs based on their re-crawl frequency with the goal to schedule the URLs in such a way that each crawl should take around one hour. The results show that we tend to underestimate the crawls resulting in overlaps of an average of 10 minutes for two consecutive crawls. While overestimating the crawl time does not cause trouble for the scheduling. However, due to the high overestimation we could add more URLs to the crawls and do currently not optimally use the available resources. Actual crawl time Overestimate (crawls) Underestimate (crawls) total crawls We presented in this seminal work our vision of an infrastructure to preserve and archive the changes on the Web of Data and outlined some core requirements for such an infrastructure. In addition, we presented our e orts in developing and researching the core component of this infrastructure and conducted two initial experiments. The rst experiments evaluated various heuristics to reschedule the crawl frequency of URLs to accurately capture the changes of the data source. Our ndings indicated that a strategy based on state-change transitions probabilities provide promising results and indications to concentrate more e orts on this in the future. The second experiment evaluated a simple rst- t bin packing algorithm to estimated the crawl time for a set of URLs based on their average domain download and crawl-delay times. Our results show that the average underestimation is very low, however the approach tends to overestimate the crawl time by large.
Our future work will concentrate in improving both heuristics with the goal of developing algorithms to optimally schedule and reschedule the crawl time of URLs so that the system is using the available resources in an optimal way and is able to capture the changes of the source on the Web of Data as timely and accurately as possible.
Acknowledgements This work was partially funded by the "Jubilaumsfond der Stadt Wien 2014".