Working Set BST

Various implementations of Balanced Binary Search Tree (BST) guaranteed membership queries in $O(\log n)$ time, where $n$ is the number of elements in some set $S$ . The working set property is a stronger requirement than $O(\log n)$ time complexity. Suppose that an item $x \in S$ is accessed $t$ queries before, then we want to perform $\text{find} (x)$ in $O(\log t)$ time.

The idea is to maintain a sequence of Balanced BST's, denoted as $T_0, T_1, T_2, ...$ . Denote the size of $T_i$ for some $i \ge 0$ as $n_i$ . Then the $i$ -th tree maintains the latest $n_i$ accessed items. The sizes of $n_i$ 's satisfy

\begin{aligned} & n_0 = 1 \\ & n_1 = 2 \\ & n_2 = 4 \\ & n_3 = 16 \\ & ... \\ & n_i = 2^{2^{i - 1} } \\ & n_{i + 1} = n_i^2 = 2^{2^i } \\ & ... \\ & n_k = 2^{2^{k - 1} } \end{aligned}

The largest tree has an index that equals to the smallest $k$ with $2^{k - 1} \ge \log n$ (assuming that $n \ge 1$ ). It implies that $k = O (\log \log n)$ . The complexities for searching an element on these trees are

\begin{aligned} & c_0 = 1 + \log 1 \\ & c_1 = 1 + \log 2 \\ & c_2 = 1 + \log 4 \\ & c_3 = 1 + \log 16 \\ & ... \\ & c_k = 1 + \log 2^{2^{k - 1}}\\ \end{aligned}

When a query $\text{find} (x)$ is invoked, we first search it on $T_0$ . If we find it successfully, we stop. Otherwise we search it on $T_1$ and so on. If $x$ is accessed $t$ queries before (and is not accessed in the latest $t - 1$ queries if $t \ge 1$ ), then it is contained in the tree $T_{i_x}$ , where

i_x \doteq \text{ the smallest non-negative integer, } s.t. \ 2^{i_x - 1} \ge t

As a sanity check, note that when $t = 0$ ( $x$ is the latest accessed item), we have $i_x = 0$ as $2^{-1} \ge 0$ . By definition of definition of $i_x$ , $x$ is not contained in any $T_i$ with $i < i_x$ . The time to search $x$ is

\begin{aligned} &(1 + \log 1) + (1 + \log 2) + (1 + \log 4) + (1 + \log 16) + ... + (1 + \log 2^{2^{i_x - 1} }) \\ &=i_x + 1 + \sum_{i = 0}^{i_x - 1} 2^{i} \\ &=i_x + 1 + 2^{i_x} - 1 \\ &=O(\log \log t) + O(\log t) \\ &=O(\log t) \end{aligned}

Finally, we need to update the trees $T_0$ , $T_1$ , ... $T_{i_x}$ to reflect the last access of $x$ . In particular, we 1) insert $x$ into $T_0$ , $T_1$ , ... $T_{i_x - 1}$ ; 2) for each $i < i_x$ , we delete the least recently accessed item; 3) update the access time of $x$ in $T_{i_x}$ .

Step 1) takes $O(\log t)$ time. To implement steps 2) and 3) in $O(\log t)$ time, we create a min-heap $H_i$ for each tree $T_i$ that keeps the the access time of items in $T_i$ . Both fetching least recently accessed item and updating access time can be performed in $O(\log n_i)$ time. Therefore, steps 2) and 3) take $O(\log t)$ time in total.