Bounding Risk

Given that web servers are autonomous and pages can change arbitrarily at any time, it is important to mitigate the risk associated with waiting a long time between refreshes. Our online revisitation policies (Sections 4.2 and 4.3) aim to refresh a page whenever the estimated utility penalty of not doing so exceeds $T$, in a best-effort manner. We wish also to guarantee that in the worst case, the utility penalty incurred without performing a refresh is at most $\rho \cdot T$, where $\rho \ge 1$ is a risk control parameter.

Let $D_{\mathit{max}}$ denote the maximum divergence value allowed under the chosen page divergence metric. ( $D_{\mathit{max}} = 1$ under our fragment staleness metric.) The maximum loss in utility incurred during $t$ time units is $t \cdot D_{\mathit{max}}$. To cap the utility loss between refreshes at $\rho \cdot T$, we restrict the refresh period $\phi_P$ to remain less than or equal to $\rho \cdot T / D_{\mathit{max}}$ at all times.