Estimating the Rate of Web Page Updates

1 Introduction

Most of the information available on the Web are autonomous and are updated independently of the clients. Estimating the rate at which Web pages are updated, is important for Web clients like Web crawlers, Web caching etc. to improve their performance. Since the sources are updated on their own, such a client does not know exactly when and how often the sources change. Web crawlers need to revisit the sources repeatedly to keep track of the changes and maintain the repository upto-date. Further, if a source is revisited before it is changed, then it will be a wastage of resources such as CPU time, file system and network bandwidth for both client and server. Such a visit is defined as a premature visit. For a client like a Web crawler with a collection of thousands of millions of such sources, it is important to schedule its visits optimally such that number of unobserved changes between the subsequent visits and the number of premature visits are minimum. Therefore, study of the changing behavior of web pages and estimating their changing rate can benefit in improving Web crawler's scheduling policy, Web page popularity measure, preprocessing the accessed schedules etc. This is the main motivation of this work. Another question that is attempted to answer in this paper is the localized rate of changes of the sources. For example, At what rate was a Web page updated during the month of January last year? How does the rate of updates change during the month of January for the last five years? This paper focuses mainly on estimating localized rate of updates rather than global update rates. Since the rate of updates of the sources may vary with time, localized estimation provides more detail, useful and accurate information.

Contrast to the previous studies [Cho and Garcia-Molina, 2003; Matloff, 2005], the process of Web page updates is modeled as time-varying Poisson process. It is because of the fact that sources are updated by its owner autonomously and independently whenever there are new developments and the rate of updates may vary with time. Therefore, it is more appropriate to assume the update process as a time varying Poisson process rather than time homogeneous Poisson process. The advantage of modeling the problem as non-homogeneous Poisson process is its wide range of flexibilities. It can be noted that homogeneous Poisson process is a special case of non-homogeneous Poisson process. A major difficulty in modeling the problem as non-homogeneous Poisson process is that it has infinitely many parameters. In particular, it is parameterized by its arrival-rate λ(t), which varies with time. To simplify the problem, the attention is restricted to certain assumptions of λ(t) i.e., constant, increasing or decreasing. Such assumption help in reducing the number of parameters. This assumption may not be correct over a long period of observations (say, over years of page update records), but reasonable over appropriate subintervals (say, over few weeks). Therefore, the whole observation space is divided into a sequence of windows of consistent behavior (see Section 4). The above assumption is reasonable as this paper is focussed more on the instanteneous page update rates.

1.1 Accessing theWeb pages

One major problem in modeling the changing behavior of Web page is that, the complete information of the sequence of updates is not available. Web pages are accessed repeatedly through normal activities such as periodic crawling of web pages. It is only possible to determine, whether a page had changed, but not possible to determine the number of changes between two subsequent accesses, which results in loss of information. The accuracy of the estimation of the rate of changes depends on how small the number of unobserved updates is.

Assuming that the Web pages are accessed periodically with a small interval τ, let m(i) be the number of page updates between the (i - 1)th and ith accesses and {t(i,1), t(i,2), t(i,3), ..., t(i,m(i))} be the time sequence of corresponding updates. The changes can be observed in the following two ways:

-Last date of change: Some Web servers provide the information about when the page was last modified. It is not possible to obtain the complete update information between accesses. In such case, we only observe t(i,m(i)) and {t(i,1), t(i,2), t(i,3), ..., t(i,m(i)-1)} are left unobserved. There is no way to obtain the unobserved information. Assuming that m(i) is small, we ignore the unobserved updates and count only one update during ((i - 1)τ, iτ] if changes occur and consider t(i,m(i)) as the renewal point.

-Existence of change: Some Web servers do not provide such information i.e., last date of change. In such case, it is only possible to determine whether the page has changed between accesses comparing with the old image of the page. We can not even determine t(i,m(i)). It could have changed any number of times anywhere between (i - 1)th access and ith access, i > 0. If changes occur, it is counted as one.

1.2 Formulating the Process

In the studies [Cho andGarcia-Molina, 2003;Matloff, 2005], the two classes of observing updates are handled separately. Unlike these studies, the observed information is preprocessed and a model is formulated to handle both the cases identically simplifying the problem. For the case of last date of change, the t(k,m(k)) is considered as the update point of the kth interval and the process of update time is formulated as {t(i) | t(i) = t(k,m(k)), i = N(kτ), i, k > 0}, where N(t) is the number of updates during the period (0, t].

For the case of existence of change, the t(k,m(k)) is not available. Assuming that sources are accessed periodically with an optimal interval, we can approximate t(i), say the middle point or the end point of the period or a point determined from an appropriate distribution. Here, the t(i) is approximated as the middle point and the process of update time is formulated as {t(i) | t(i) = (k - 1)τ + τ/2, i = N(kτ), i, k > 0}, where N(t) is the number of observed updates during the period (0, t].

Thus, the time sequence {t(i) : i = 0, 1, 2, ...} represents the sequence of the update points for both the cases satisfying the properties t(0) = 0 and t(i) < t(i + 1), where t(i) is the time of the ith update. Since the client does not know exactly when and how often the Web page updates, the sequence {t(i) : i = 0, 1, 2, ...} is an independent and identically distributed random process, which is often modeled as a Poisson process in several studies [Brewington and Cybenko, 2000; Cho and Garcia-Molina, 2003; Matloff, 2005]. This study also assumes the model as a Poisson process, but as a nonhomogeneous Poisson process. One of the advantages of modeling the process as a non-homogeneous Poisson process includes the ability to determine the instantaneous update rate i.e., λ(t). In summary, this paper makes the following contributions:

-handles the last date of change and existence of change cases identically.

-models the system as a non-homogeneous Poisson process.

-proposes two λ(t) estimators namely Weibull estimator and Duane plot estimator and compares the estimates using various datasets with the estimators proposed in existing literatures.

The rest of the paper is organized as follows. Section 2 discusses non-homogeneous Poisson distribution. In Section 3, we discuss different estimators of rate of updates. In Section 4, we divide the whole observation space into windows of consistent behavior. Experimental verifications are discussed in Section 5. Then we conclude the paper in Section 6.

2 Non-homogeneous Poisson Process

A non-homogeneous Poisson process over [0,∞] is determined by a rate function λ(t) ≥ 0, known as intensity density of the process (see Chapter 6, Trivedi [Trivedi, 1982]). Let N(T ) be the number of updates during the time period (0, T ]. Then, the intensity function of the process, i.e. mean number of updates during the period (0, T ] is defined as follows.

Now, the probability that the number of updates during the period (0, T ] equals to k, is given by

for k = 0, 1, 2, ... The Time homogeneous Poisson process is a special case, where λ(t) = λ for all time instances t ≥ 0. Now, the probability of N(T ) becoming zero is equal to Pr[N(T) = 0] = e-μ(T) . Thus we can write its cumulative distribution function (cdf) as F (T ) = 1 -e-μ(T) and its probability density function (pdf) as f(T ) = μ′ (T )e-μ(T ) = λ(t)e- ∫ T 0 λ(t)dt . Using the expression of F(t) and f(t) above, the instantaneous λ(t) can be expressed as

3 Estimating λ(t)

As stated in Section 1, the whole observation space is divided into a sequence of windows of consistent behavior. A window is a sequence of update points satisfying the property that t(i) > t(i1), where t(i) is the time of the ith update. Since the sequence of update points are independent and identically distributed and satisfies the memoryless property, each window can be processed independently to determine the λ(t).

Definition 1 A window is said to be consistent, iff either one of the followings is true.

1. λ(t(i)) < λ(t(j)), ∀i < j, j > 0 i.e., increased

2. λ(t(i)) > λ(t(j)), ∀i < j, j > 0 i.e., decreased

3. λ(t(i)) = λ(t(j)), ∀i < j, j > 0 i.e., constant

3.1 Intuitive Measure: N(t)/t

If N(t) is the number of updates during the period (0, t], the rate of updates at the time t is λ(t) = N(t)/t and instantaneous mean time between updates (MTBU) at time t, MTBU(t) = t/N(t). This estimation is suitable when the window satisfies the third consistency property i.e., the rate of update is constant. It is the biased estimation of λ(t) in a homogeneous Poisson process [Cho and Garcia-Molina, 2003].

3.2 Estimation usingWeibull Distribution

If the rate of update is either increasing or decreasing or constant, the Weibull distribution is a good mechanism to model the process. The two parameter Weibull pdf is given by

where β is known as shape parameter and η is known as scale parameter and β, η > 0 (see Chapter 2, Patrick [O'Connor, 2002], [Lieblein, 1955]). Then its cdf is given by F(t) = 1 - e-(t/η)β . Substituting equation 2 and F (t) in equation 1, we get

From the study [Lieblein, 1955], we have (1) if β = 1, then λ(t) = 1/η, a constant (the process reduces to the homogeneous Poisson process), (2) if β < 1, then λ(t) decreases as t increases and (3) if β > 1, then λ(t) increases as t increases. A window is always in one of the above three states. Therefore, Weibull's distribution is obviously a good choice of estimating λ(t).

In [Tsokos, 1995], the author found the relationship between MTBU(t) and λ(t) as follows.

Thus, 1/λ(t) defines the bounds of MTBU(t). Now our task is to estimate the parameters β and η. We estimate these two parameters using maximum likelihood estimator as given below. The conditional pdf of the ith event given that the (i - 1)th event occurred at ti-1 is given by f(ti | ti-1) = βη ( ti η )β-1 e1 ηβ (tβi -tβi-1 ) , ti-1 < ti. Now, the likelihood

function can be defined as

Taking log on both sides we get

Assuming c = 1/ηβ , we can write

Taking partial derivative w.r.t. c and equating to zero, we get

Again, taking partial derivative w.r.t. β and equating to zero, we get

Lemma 1 ˆ β is biased for small value of n and equal to n n-2 β

Proof As reported in [Calabria et al., 1988], 2nβ/ˆ β ∼ Z, where Z is a chi-square random variable with 2(n - 1) degree of freedom. Then we can write ˆ β = 2nβ Z = 2nβ Γ(n-1)2n-1 tn-2 e-t/2 . Now, the expectation of ˆ β can be derived as E[ ˆ β] = 2nβ Γ(n-1)2n-1 ∫ ∞ 0 tn-3 e-t/2dt = 2nβ (n-2)Γ(n-2)2n-1 Γ(n - 2)2n-2 = n n-2 β. If n is small, then ˆ β is biased. ✷

Now, Lemma 1 suggests correcting the ML by a factor of (n - 2)/n and thus obtain

We can easily prove that E[ ˜ β] is unbiased i.e., E[ ˜ β] = E[ n-2 n ˆ β] = n-2 n E[ ˆ β] = β. Thus we get ˜ η = tn n1/ ˜ β . Substituting the value of ˜ β and ˜ η in equation 3, we determine the value of ˜λ(t) = n˜ βt ˜ β-1/t ˜ βn. In [Calabria et al., 1988], it is proved that ˜λ(t) is less biased i.e., E[˜λ(t)] = λ(t)(n - 2)/(n - 3). Again, we correct ˜λ(t) by a factor (n - 3)/(n - 2) to get an unbiased estimation and thus obtain

It can easily be proved that E[ˇλ(t)] is unbiased i.e., E[ˇλ] = E[ n-3 n-2 ˜ λ(t)] = n-3 n-2 E[˜λ(t)] = λ(t). We use this estimator in our experiment. Another unbiased estimate of λ(t) is ¯λ(t) = (n - 3) ˆ βt ˆ β-1/t ˆ βn, which is obtained by correcting ˆλ(t) by a factor of (n - 3)/2 [Calabria et al., 1988]. Once we get windows of consistent behavior (see Section 4), we can thus estimate λ(t).

3.3 Estimation using Duane Plots

In this Subsection, we discuss another λ(t) estimator using Duane plot [Duane, 1964].

Property 1 Let MTBU(ti) = ti i , i > 0 be the cumulative mean time between updates at ith update. If the sequence of MTBU(ti) is either increasing or decreasing or constant as i increases and if we plot a graph between MTBU(ti) along y-axis and ti along x-axis on log-log graph paper, the points tend to line up following a straight line. This plot is known as Duane Plot.

The slope of the straight line passing through points is known as Duane plot slope. From the straight line, we can write logMTBU(t) = log α + γ log t, where γ is the Duane plot slope and α is the intercept when t = 1. Equating MTBU to its expected value, we get MTBU(t) = αtγ . Similarly, cumulative λ(t) can be written as λ(t) = 1α t-γ . Now, the slope γ can be calculated as

As we consider the λ(t) estimation only within the consistent windows, the Duane plot can be applied to estimate the λ(t). This estimation works fine as long as both the points (MTBU(ti), ti) and (MTBU(tj), tj) are on the best straight line through the points. But, it is not the case in reality. Therefore, the straight line which is closest to all the observed points is considered and the γ is the slope of the obtained straight line. The simple linear regression is applied to find the best straight line closest to all the observed points.

3.4 Estimation using Linear Regression

If we consider a consistent window with either constant or increasing or decreasing λ(t), linear regression is an effective mechanism to estimate λ(t). Under such conditions, the relationship between λ(t) and t can be defined by a straight line. Linear regression defines a straight line closest to the data points. We can define the equation of the closest straight line as y′ = a + bx, where a and b are regression coefficients and defined as a = y - bx and b = ∑ (xi-x)(yi-y) ∑ (xi-x)2 . We apply simple linear regression to get the best straight line closest to all the observed points in the Duane plot. If we consider x = log ti and y = logMTBUc(ti), then b is equal to the slope of the Duane plots γ and a is equal to the intercept α.

3.5 Measuring error

An error at a point i is defined as the difference between the observed value and predicted value at that point i i.e., ▽(i) = fobserved(i) - fpredicted(i). The error in measuring λ(t) is minimum if error in measuring MTBU(t) is minimum and vice versa. Again, overall error in MTBU(t) is minimum when ∑N(t) i=1 ▽(i) = ∑N(t) i=1 (MTBU(t(i)) - (t(i) - t(i - 1))) is minimum. Thus, ∑N(t) i=1 ▽(i) can be used as a measure to compare different estimations of λ(t). The λ(t) with the minimum ∑N(t) i=1 ▽(i) is considered as the best estimate. But, in the case of linear regression mechanism ∑i ▽(i) = 0. To avoid this problem, we can use mean of square error MSE = ∑ni=1 ▽(i)2/n as a measure to com-

pare different estimators.

4 Generating Consistent Window

In reality, most of the Web page update period sequence is inconsistent. It is found to be a sequence of constant, increasing and decreasing over subsequent period of times in any order. In this Section, a procedure to generate the consistent windows (as define in Definition 1) out of a sequence of update points is discussed. First the localized λ(t) is defined. If W be the set of update points, then the average number of update points within the window W can be defined as μ(W) = ∫W λ(x)dx < ∞, where λ(x) is locally integrable. Now the localized λ(x) can be defined as λ(x) = limW→x P r(N(W )=1) |W | , where N(W) denotes the number of updates within W and x is an update point. Thus, it is necessary for the windowW to be consistent so as to be able to predict Pr(N(W) = 1).

Now, the total observation space is divided into windows Wi of consistent MTBU i.e. either constant or increasing or decreasing in nature. the length of a window | Wi(k) | is defined by (tj+k - tj), j > 0, where Wi(k) starts just after j th update and k is the number of update points within the window. The accuracy of the estimation depends on the nature of the update points within the window. So, how do we decide the window size? The important factor in deciding the window size i.e., k is the number of consistent points within the window, not | Wi(k) |.

Consistent window: The initial window consists of the last (first) three update points and extended backward (forward). A window is always in one of the three states, either constant or increasing or decreasing state. The window extends if the next point at tj is consistent with the state of the current window. We often do not find consistent windows of large size. To increase the size of the windows, we allow few inconsistent update points within the window with a limit on the amount of discrepancies. Even if an update point tj is not exactly consistent with the current state, we consider the tj as a consistent point if the amount discrepancy is below some threshold value, otherwise we create the next window.

5 Experimental Evaluation

The comparisons of different estimators are based on both synthetic datasets (collected from the UCLA WebArchive project data available at http://webarchive.cs.ucla.edu/) and real Web datasets. Synthetic datasets consist of 3,00,000 pages' records and each record contains 200 access units. The real Web datasets were collected locally. The 27034 number of frequently access Web pages were identified from our local proxy server log file. These pages were crawled every day for two months (12th April, 2006 to 12th June, 2006) to keep track of the changes.

Table1 shows the characteristics of the two datasets. The pages having less than four update points during the observation period are ignored. The proposed estimators are compared with the estimators proposed in [Cho and GarciaMolina, 2003] and [Matloff, 2005]. The λ proposed by Cho et al. can be stated as λcho = - 1 τ log( n-X+0.5 n+0.5 ), where n is the number of intervals of τ and X is the number of intervals with at least one update point. Again, the λ proposed by Matloff N. can be stated as λnorman = - 1 τ log(1 - Mn n ), where n is the number of intervals of τ and Mn is the number of intervals with at least one unobserved update point. To get the best result out of the available information, τ is set to 1.

The experimental evaluations consists of two parts. In the first part, the localized λ(t) is estimated using the estimators discussed in Section 3 from the sequence of data points in the observation space. The sequence of consistent windows are generated using the procedure discussed in Section 4. The consistent windows with a minimum size of four update points are considered. If the size of the window is less than four, then one half is merged with the left window and another half with the right window in the sequence introducing some discrepancies. For each window, the λ(t) is estimated at every update point t using different estimators. For simplicity, MTBU(t) is approximated as MTBU(t) ∼ 1/λ(t) and then regenerate the whole observation space again using the estimated MTBU(t). The difference between actual update point and estimated update point is considered as an error. The errors in every estimated update points are recorded and the average MSE for each window is determined to compare the accuracy of different estimators.

Table 2 compares the average MSE of different estimators in terms of different window classes. The proposed Weibull estimator outperforms other estimators for all the cases. For the case of constant state windows, all these four estimators performs equally well with very small average MSE. But, Weibull estimator outperforms the rest with significantly smaller average MSE for both increasing and decreasing state windows. In Table 3, the percentage of the number of windows out of the whole windows, in which row estimator outperforms the column estimator, is shown. It shows that Weibull estimator outperforms the rest in 91.5% of the whole windows for synthetic datasets and in 90.6% of the whole windows for real Web datasets. Whereas the previous estimators λcho and λnorman outperforms the rest almost in 0% for both synthetic and real datasets. Again we compare different estimators in terms of the average MSE for different window sizes as shown in Figure 1. It clearly shows that error decreases as we increase the size of window. For the larger size windows, all estimators perform equally well (still Weibull outperforms by smaller extents), but for the smaller size windows, Weibull outperforms the other estimators by almost double.

The main motivation behind investigating localized λ(t), rather than global λ is to use the piecewise information to improve the prediction of future update points. For example, the trend in λ(t) during the month of January for last five years can be used (or combined with recent trend) to predict future λ(t) of next January. Due to not having enough datasets to make use of such information, such study is left as the future work.

However in the second part of the experiment, the effectiveness of different estimators is investigated by predicting the future update points from the past information running a simulation program. Simulation starts with first consistent window in the observation space and based on this window, the next update point is predicted. Then the window is extended to include the newly predicted point and again predict the next update point and so on. As pointed out in Section 1, an efficient estimator should be able to detect good amount of update points with minimum amount of resource consumption. Each premature visit is a wastage of resources such as CPU time, file system, network bandwidth etc. (see Section 1). To compare different estimators , a measure of precision is defined and stated as follows.

The precision of an estimator represents the probability of detecting an update per visit. It is reasonable to conclude that estimator with the highest precision is the best estimator, with the highest probability of detecting update points. There are 744385 number of update points in real dataset and 30931883 in synthetic dataset. Table 4 shows the comparisons among the four estimators in terms of the percentage of updates detected, premature visits, precision and number of visits. Though the λcho and λnorman estimators detect the highest number of the update points, it is very expensive, almost 42% (36%) of the total visits over real (synthetic) dataset are premature visits. Moreover, the number of visits scheduled by both λcho and λnorman estimators are very large compared to the number of visits scheduled by Weibull estimator. Whereas Weibull estimator has the highest precision i.e. the probability of detecting updates per visit, almost 0.70 (0.76) for real (synthetic) datasets and minimum number of visits. If the number of visits is normalized, Weibull estimator detects the highest number of update points, next followed by Duane, then λnorman and λcho. If the number of visits is normalized to the number of visits of Weibull estimator, both the estimotors λcho and λnorman detect only around 62% (60%) and Duane estimator detects around 68% (66%) for synthetic (real) datasets. Note that the best policy is the one that detects the highest number of update points with minimum resource consumption, in other word highest number of update points detected from the same number of visits. Therefore, Weibul estimator outperforms other estimators.

6 Conclusions

This paper models the process of web page updates as nonhomogeneous Poisson process. In a scenario with inconsistent rate of updates, piecewise estimation provides more detail and useful information compared to global estimation. In the study, the whole observation space is divided into independent consistent windows to estimate localized rate of updates. Two update rate estimation mechanisms namely Weibull and Duane plot are proposed. Tests on both synthetic and real datasets confirm that Weibull's estimator outperforms Duane plot and both the existing estimators λcho and λnorman while estimating localized rate of updates. While investigating the effectiveness of using these estimators to predict future update points, Weibull estimator has highest probability of detecting update points.