Elias Neuman-Donihue, University of Rochester, May 2020

A small correction to Li et. al.’s paper: in section 3.2, the length of a time window is defined as “its end time minus its start time plus one.” However, in section 3.2.1, there is a reference to “windows of length k from 0 $\leq$ k $\leq$ n,” the lower bound of which refers to windows with their end index before their start. This also leads to some mathematical inconsistencies in sections 3.2.1 and 3.2.2.

One such error is the calculation of reuse(1): by the stated definition, an interval of length k=1 has only one allocation, so the reuse should be one if the window also contains a matching free operation and 0 otherwise. Therefore, since there are a total of n windows of length 1, the average reuse of all such windows should be:

$reuse(1)$ $=\frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}$

However, by the formulae stated in 3.2.2:

$reuse(1)$ $=\frac{\sum_{i=1}^{m}I(e_i-s_i=1)s_i - \sum_{i=1}^{m}I(e_i-s_i=1)(s_i + 1) + 2\sum_{i=1}^{m}I(e_i-s_i=1)}{n}$

$reuse(1)$ $=\frac{\sum_{i=1}^{m}I(e_i-s_i=1)}{n}$ $\neq$ $\frac{\sum_{i=1}^{m}I(e_i-s_i=0)}{n}$

In order to standardize the equations with the provided definition of window length, a few changes must be made:

In Eq. 1 and Eq. 2, every instance of $e_i - s_i \le k$ should instead read $e_i - s_i < k$

Then in Eq. 2,
$Z(k)=$ $\frac{\sum_{i=1}^{m}I(e_i - s_i < k) \cdot k}{n-k+1}$

The recursive equations should then read

$X(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)s_i$

$X(k) = X(k-1) + \sum_{i=1}^{m}I(s_i\ge n-(k-1)) + \sum_{i=1}^{m}I(e_i-s_i+1=k)min(n-k, s_i)$

$Y(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)e_i$

$Y(k) = Y(k-1) + \sum_{i=1}^{m}I(e_i\le k-1) + \sum_{i=1}^{m}I(e_i-s_i+1=k)max(k, e_i)$

$Z(1) = \sum_{i=1}^{m}I(e_i - s_i = 0)$

$Z(k) = Z(k-1) + \sum_{i=1}^{m}I(e_i-s_i < k) + \sum_{i=1}^{m}I(e_i-s_i+1=k) \cdot k$

(Sent to my class on the exam day)

NY Times collects and publishes New York city stories submitted by its readers at https://www.nytimes.com/column/metropolitan-diary.  The May 3 entry was Christopher Fryer who remembered “joys of city life walking every day from our apartment on the Upper West Side through Central Park, and then down Sixth Avenue to my office at 46th Street”, found “a shining Lincoln head on the penultimate step”, “paused to pick it up, being careful not to impede either the people coming up behind me or those who were heading down into the station”, and “a man on his way down the stairs spoke without breaking stride.

“Hey,” he said. “ I saw one of those at 125th Street. If you hurry you can probably get that one, too.”