Change Profiles

A change profile of page $P$ consists of a sequence of (time, divergence) pairs, starting with a base measurement ($t_B$, $0$) and followed by zero or more subsequent measurements in increasing order of time. Time $t_B$ is called the base time, and represents the time at which the change profile was initiated. Each subsequent measurement corresponds to a refresh event performed subsequently to $t_B$ by the revisitation policy. All divergence values in the profile are computed relative to the base version $P(t_B)$.

An example change profile is: $\langle$ (10, 0), (12, 0.2), (15, 0.2), (23, 0.3) $\rangle$. This profile indicates that the refresh times for this page include 10, 12, 15 and 23, and that $D(P(10), P(12)) = 0.2$, $D(P(10), P(15)) = 0.2$, and
$D(P(10), P(23)) = 0.3$. $P(10)$ is the base version; $10$ is the base time.

Our online revisitation policies initiate and maintain change profiles in the following manner. Each time a new refresh of $P$ is performed, a new change profile is created with base time $t_B$ set to the time of the refresh. Each subsequent time $t$ that $P$ is refreshed, the profile is extended with the pair ($t$, $D(P(t_B), P(t))$).

Up to $h$ change profiles are maintained simultaneously, each with a different base version. ($h$ is a positive integer parameter that governs the amount of history tracked by the policy.)