Estimating Change Rates from Interval-Censored Fetches

A crawler that revisits every page at the same interval spends most of its budget re-fetching pages that have not changed and misses changes on pages that change hourly. The fix is to give each URL its own revisit interval, derived from how often that URL has been observed to change. The derivation is where the difficulty lives, because the observation is not “the page changed at time t”. It is “the page was different when I looked, and I do not know when it became different.”

That distinction is the whole subject. A naive estimator treats each fetch as a Bernoulli trial and computes the fraction of fetches that found a change. Under that model, a page fetched ten times with one observed change has a change probability of one tenth, and the natural revisit interval is ten times the fetch interval. The estimate is biased in a specific direction, and the bias grows as the fetch interval grows, which is exactly backwards from what the scheduler needs.

What the observation actually is

Model a page’s content as changing at random times, with changes arriving as a Poisson process of rate λ, measured in changes per unit time. Between changes the content is stable; the crawler samples at instants and sees the current state.

When the crawler fetches at time t and the content differs from what it held from time s, the change occurred somewhere in the open interval (s, t). The observation is an interval, not a point. When the content is the same at both times, the observation is that no change occurred in (s, t). This is interval censoring, and ignoring it is what produces the naive estimator’s error.

The magnitude of the error depends on the ratio of the fetch interval to the true change interval. If the crawler fetches much more often than the page changes, censoring costs little: the change is localized to a small window and the estimate is nearly right. If the crawler fetches rarely relative to the change rate, a single observed change may represent five actual changes that reverted or overwrote each other in between, and the fraction-of-fetches estimator will systematically underestimate λ. The scheduler then lengthens the interval, which worsens the censoring, which lowers the estimate further. The feedback loop converges to a crawler that has decided a busy page is static.

The likelihood, written out

For a single interval of length Δ during which no change was observed, the probability under a Poisson process is exp(−λΔ). For an interval in which at least one change occurred, the probability is 1 − exp(−λΔ). A sequence of n intervals with c observed changes therefore has likelihood

$$L(\lambda)=\prod_{\text{unchanged}} e^{-\lambda \Delta_i}\prod_{\text{changed}}\left(1-e^{-\lambda \Delta_i}\right)$$

and the maximum-likelihood estimate solves a one-dimensional equation with no closed form when the intervals are unequal. With equal intervals Δ, the estimate reduces to

$$\hat{\lambda}=-\frac{1}{\Delta}\ln\left(1-\frac{c}{n}\right)$$

which is the corrected version of the naive fraction. For c = 1 and n = 10, the naive estimate is 0.1/Δ and the corrected one is about 0.105/Δ — nearly identical, because with a single change the censoring correction is small. The two diverge sharply as the observed fraction rises: at c/n = 0.5 the corrected estimate is 0.69/Δ, nearly forty percent higher than the naive 0.5/Δ, because half the intervals contain at least one change and some contain several.

The formula also exposes the degenerate case. When every interval shows a change, c = n, the logarithm is undefined and the likelihood is maximized as λ goes to infinity. That is not a numerical nuisance; it is the honest statement that a page changing on every visit carries no information about its rate above the sampling frequency. The scheduler must cap such pages at the shortest feasible interval rather than extrapolate.

Why a prior is not optional

With few observations the maximum-likelihood estimate is either zero, since every page starts with no observations and a page fetched once without change has c = 0, giving λ̂ = 0 and an infinite revisit interval, or wildly variable. A page that happened to change on its first two fetches gets a very high rate, and a page that did not gets zero, and both estimates rest on two samples.

A Gamma prior on λ fixes both problems and has a convenient property: the Gamma is conjugate to the Poisson, so the posterior after observing a total of c changes over a total exposure of T time units is Gamma(α + c, β + T), where α and β parameterize the prior. The posterior mean is (α + c)/(β + T), which is a smoothed ratio: the prior acts as a pseudocount of α changes observed over β units of time, and its influence fades as real observations accumulate.

The choice of α and β encodes a prior belief about typical change rates, and it is the only place where a crawler’s operator injects judgement. A prior mean of one change per week corresponds to α/β = 1/7 per day, with α around 1 so the prior is weak. Setting α larger makes the estimate more conservative, so new URLs start with a moderate assumed rate and take longer to be reclassified, and setting it smaller makes the crawler explore more aggressively.

from dataclasses import dataclass

@dataclass
class PageState:
    alpha: float = 1.0        # prior changes
    beta: float = 7.0         # prior exposure, in days
    last_fetch: float = 0.0

    def observe(self, now, changed):
        # exposure-based update: the interval counts whether or not it held
        # a change, so intervals containing several changes count once.
        self.beta += now - self.last_fetch
        if changed:
            self.alpha += 1.0
        self.last_fetch = now

    def rate(self):
        return self.alpha / self.beta      # posterior mean, changes per day

    def next_check(self, now, factor=1.0):
        lam = max(self.rate(), 1e-6)
        # mean wait to the next change is 1/lam
        return now + factor / lam

This update is the exposure-based approximation, not the exact interval-censored likelihood. It counts each interval as at most one change, which is the bias the likelihood formula removes. Two things keep it usable. The prior contributes a fixed amount of exposure that dominates while the page has few observations, so a fresh URL does not get an extreme rate. And the interval a URL is actually scheduled at is derived from the rate estimate, so a persistently underestimated rate shows up as repeated changes and pulls the estimate up, at the cost of some latency.

The factor deserves comment. Checking exactly at the expected time to next change means roughly 63 percent of visits will find the page already changed, since the exponential waiting time has that much mass below its mean. A scheduler that wants to catch changes promptly uses a factor below one; one that wants to minimize fetches per detected change uses a factor above one. Neither is universally right, and the choice belongs to the objective being optimized rather than to the estimator.

The estimator’s blind spots

Four properties of real pages break the Poisson assumption, and each breaks it in a different direction.

Periodicity. A page updated every Monday at 09:00 is not a Poisson process; it is a deterministic one with jitter. A Poisson model fitted to observations of it produces a rate that is roughly right on average and useless for scheduling, because the optimal revisit time is shortly after Monday 09:00, not at a fixed expected interval. The remedy is to keep per-page observation history and look for periodicity in it, which is a separate and much more expensive estimation problem, and one that only pays off for pages whose traffic justifies the bookkeeping.

Burstiness. News pages and pages generated from feeds change many times in a short window and then not at all. A Poisson rate fitted across the whole history underestimates the rate during the burst and overestimates it after. Exponential smoothing of the rate, weighting recent observations more heavily, tracks bursts better and gives up the stability of the conjugate update.

Non-monotone content. A page that changes and then reverts is observed as unchanged at both endpoints if the crawler looks before and after. The Poisson model with binary observation cannot see the change at all. Content digests taken at every fetch record the sequence, but only for changes that persist long enough to be sampled.

Metadata-only change. If change is detected by comparing a validator or a digest of the whole page, a rotating advertisement banner marks the page as changed every visit. Change detection should compare the content that matters for the index, which usually means the extracted text or a normalized digest, not the raw bytes. The validators themselves come from the response headers, and their reliability is a precondition for any estimate built on them; the revalidation mechanics are where that reliability is decided.

From rate to schedule

Given a per-URL rate, the scheduler’s decision is which URL to fetch next. The quantity that makes the decision well-posed is expected staleness per unit of politeness budget. For a page with change rate λ, the probability it has changed by time t after the last fetch is 1 − exp(−λt), and the expected staleness grows roughly linearly in t for small λt. Fetching it resets the staleness to zero. The value of a fetch is therefore proportional to the accumulated staleness, which is higher for pages with high λ and for pages not fetched for a long time.

That gives the familiar rule: prioritize by λ times elapsed time since last fetch, which is a priority that grows continuously and thus ensures no URL is starved indefinitely. Multiplying by an importance weight, whether page rank, traffic, or whatever the index values, turns the rule into the general refresh policy, and the weights are where a crawler’s editorial judgement enters.

The estimator and the scheduler must agree on what λ means. If the estimator produces changes per day and the scheduler treats it as a probability per fetch, the intervals are wrong by a factor equal to the fetch interval. Units are the least interesting part of the design and the most common source of a schedule that looks plausible and behaves incoherently.

One structural caveat closes the loop. Every estimate is conditioned on the fetches that produced it, and those fetches were scheduled by earlier estimates. A page that was rarely fetched has few observations, a wide posterior, and a rate dominated by the prior; the scheduler may then avoid it, which keeps the posterior wide forever. Any estimator coupled to its own sampling policy needs an explicit exploration allowance — a floor on revisit frequency, or periodic random sampling — or it will permanently misjudge the pages it happened to sample least. The same failure appears at the level of the whole crawl whenever the frontier’s growth outpaces the fetch rate, which is why traps and unbounded URL spaces have to be handled before the freshness model can be trusted.