models[^6]. We show that a unified bound with “bounded time-window” holds in the BST model:

\[thm: weak UB\] For every integer $\ell \geq 1$, every sequence $X$ and some fixed function $\beta(\cdot)$, $${\mbox{\sf OPT}}(X) \leq \beta(\ell) \cdot {\mbox{\sf UB}}^{\ell}, \mbox{~~where~~~~} {\mbox{\sf UB}}^{\ell} = \sum_t \min_{t'\in [t-\ell,t)} \log \big(|x_t - x_{t'}| + \rho_t(x_{t'})\big) .$$

Observe that ${\mbox{\sf UB}}(X) = {\mbox{\sf UB}}^{m}(X) \leq \cdots \leq {\mbox{\sf UB}}^1(X) = {\mbox{\sf DF}}(X)$. Prior to our work it was not known whether the theorem holds when $\ell=2$, i.e. no known BST property subsumes this property even when $\ell =2$. Thus, Theorem \[thm: weak UB\] establishes the first BST property that combines the efficiencies of time- and keyspace-proximity without an additive term.[^7]

Recently Bose et al. [@BoseDIL14] introduced the *lazy finger* property, ${\mbox{\sf LF}}(X) = \min_R \sum_{i} d_R(x_i,x_{i+1})$. Here distance is measured in a static reference BST $R$, optimally chosen for the entire sequence. The lazy finger bound can be visualized as follows: accesses are performed in the reference tree by moving a unique finger from the previously accessed item to the requested item. The lazy finger property is rather strong: Bose et al. show that it implies the dynamic finger and static optimality properties, which 