Change Detection and Notification of Webpages: A Survey <s> Scheduling Algorithms <s> A robot is deployed by a Web search engine in order to maintain the currency of its data base of Web pages. This paper studies robot scheduling policies that minimize the fractions $r_i$ of time pages spend out-of-date, assuming independent Poisson page-change processes, and a general distribution for the page access time $X$. We show that, if $X$ is decreased in the increasing-convex ordering sense, then $r_i$ is decreased for all $i$ under any scheduling policy, and that, in order to minimize expected total obsolescence time of any page, the accesses to that page should be as evenly spaced in time as possible. We then investigate the problem of scheduling to minimize the cost function $\sum c_i r_i,$ where the $c_i$ are given weights proportional to the page-change rates $\mu_i$. We give a tight bound on the performance of such a policy and prove that the optimal frequency at which the robot should access page $i$ is proportional to $\ln (h_i)^{-1}$, where $h_i := {\rm E}e^{-\mu_iX}.$ Note that this reduces to being proportional to $\mu_i$ when $X$ is a constant, but not, as one might expect, when $X$ has a general distribution. Next, we evaluate randomized accessing policies whereby the choices of page access are determined by independent random samples from the distribution ${f_i}$. We show that when the weights $c_i$ in the cost function are proportional to $\mu_i$, the minimum cost is achieved when $f_i$ is proportional to $(h_i)^{-1} - 1$. Finally, we present and analyze a heuristic policy that is especially suited to the asymptotic regime of large data bases. <s> BIB001 </s> Change Detection and Notification of Webpages: A Survey <s> Scheduling Algorithms <s> A key challenge endured when designing a scheduling policy regarding freshness is to estimate the likelihood of a previously crawled webpage being modified on the web. This estimate is used to define the order in which those pages should be visited, and can be explored to reduce the cost of monitoring crawled webpages for keeping updated versions. We here present a novel approach to generate score functions that produce accurate rankings of pages regarding their probability of being modified when compared to their previously crawled versions. We propose a flexible framework that uses genetic programming to evolve score functions to estimate the likelihood that a webpage has been modified. We present a thorough experimental evaluation of the benefits of our framework over five state-of-the-art baselines. <s> BIB002 </s> Change Detection and Notification of Webpages: A Survey <s> Scheduling Algorithms <s> Accurate prediction of changing web page content improves a variety of retrieval and web related components. For example, given such a prediction algorithm one can both design a better crawling strategy that only recrawls pages when necessary as well as a proactive mechanism for personalization that pushes content associated with user revisitation directly to the user. While many techniques for modeling change have focused simply on past change frequency, our work goes beyond that by additionally studying the usefulness in page change prediction of: the page's content; the degree and relationship among the prediction page's observed changes; the relatedness to other pages and the similarity in the types of changes they undergo. We present an expert prediction framework that incorporates the information from these other signals more effectively than standard ensemble or basic relational learning techniques. In an empirical analysis, we find that using page content as well as related pages significantly improves prediction accuracy and compare it to common approaches. We present numerous similarity metrics to identify related pages and focus specifically on measures of temporal content similarity. We observe that the different metrics yield related pages that are qualitatively different in nature and have different effects on the prediction performance. <s> BIB003 </s> Change Detection and Notification of Webpages: A Survey <s> Scheduling Algorithms <s> Domain-specific Web crawlers are effective tools for acquiring information from the Web. One of the most crucial factors influencing the efficiency of domain crawlers is choice of crawling strategy. This article describes and compares several strategies for domain specific Web crawling. It concentrates particularly on scheduling algorithms which determine order of crawling URLs collected by the crawler. The objective of these strategies is to download the most relevant Web pages in an early stage of the crawl. In the paper there are presented four different algorithms which are compared using several metrics. <s> BIB004
Among the important research problems observed in the web information retrieval domain, the scheduling process of visiting webpages along hierarchies of links has become significant. Frequency of change may differ in different webpages as they get updated at different time schedules. Certain webpages such as wiki pages may get updated rarely whereas news websites and blogs may get updated more frequently. To crawl these webpages more efficiently, dynamic mechanisms are required to detect the change frequency and create checking schedules accordingly. Users will be notified immediately after changes have occurred to webpages that they are interested in. This will ensure computational resources are used in an optimal manner. Various solutions have been proposed to determine optimal webpage crawling schedules based on different statistical frameworks. Work done in BIB001 ] has described about crawler scheduling policies by assuming independent Poisson page-change processes. Studies carried out in have addressed the problem of determining the optimal number of crawls per page by using a staleness metric and Poisson process. Work done in  has proposed a technique to detect optimal crawl frequencies and theoretical optimal times to crawl webpages based on probability, resource allocation theory and network flow theory. Various scheduling strategies for web crawling have been studied and compared in ]. The authors have collected data from 3.5 million webpages. A web graph has been created using the collected data and different scheduling policies have been simulated. The scheduling process consists of two parts: "ordering the queue of websites (long-term scheduling)" and "ordering the queues of individual webpages (short-term scheduling)" ]. The following "long-term scheduling" strategies have been considered for the study: "optimal", "depth", "length", "batch" and "partial" ]. However, the strategies which have been considered cannot determine the temporal aspects such as how frequently webpages are undergoing changes and prioritize the crawls accordingly. Evolutionary programming techniques such as genetic programming BIB002 can be used to solve this shortcoming by facilitating schedulers to rank webpages according to how likely they are being modified. Work carried out in BIB003 , have highlighted the importance of an algorithm to predict changing web content, where it is useful in designing an optimum crawling strategy that will re-crawl pages when it is necessary. The authors have proposed an algorithmic framework for predicting webpage changes. The authors have claimed that the use of page content and related pages has significantly improved prediction accuracy. However, it can be computationally expensive to identify related pages within a general web crawling process. "Scheduling algorithms for domain specific web crawling" have been compared in BIB004 ]. Focus has been made on "scheduling algorithms" that identify the order of URLs to be crawled. Four algorithms, "depth first search", "breadth first search", "best first search" and "best n-first search" BIB004 ] have been compared. These have been evaluated based on a metric which involves the number of relevant links found. According to the experiments carried out, best first search has shown the best performance whereas best n-first algorithm has performed significantly worse. However, algorithms may get affected as webpages are crawled even though nothing has changed, where computational resources are used inefficiently.