13.3 YFastTrie: A Doubly-Logarithmic Time SSet

The XFastTrie is a big improvement over the BinaryTrie in terms of query time--some would even call it an exponential improvement--but the $ \mathtt{add(x)}$ and $ \mathtt{remove(x)}$ operations are still not terribly fast. Furthermore, the space usage, $ O(\ensuremath{\mathtt{n}}\cdot\ensuremath{\mathtt{w}})$, is higher than the other SSet implementation in this book, which all use $ O(\ensuremath{\mathtt{n}})$ space. These two problems are related; if $ \mathtt{n}$ $ \mathtt{add(x)}$ operations build a structure of size $ \ensuremath{\mathtt{n}}\cdot\ensuremath{\mathtt{w}}$ then the $ \mathtt{add(x)}$ operation requires on the order of $ \mathtt{w}$ time (and space) per operation.

The YFastTrie data structure simultaneously addresses both the space and speed issues of XFastTries. A YFastTrie uses an XFastTrie, $ \mathtt{xft}$, but only stores $ O(\ensuremath{\mathtt{n}}/\ensuremath{\mathtt{w}})$ values in $ \mathtt{xft}$. In this way, the total space used by $ \mathtt{xft}$ is only $ O(\ensuremath{\mathtt{n}})$. Furthermore, only one out of every $ \mathtt{w}$ $ \mathtt{add(x)}$ or $ \mathtt{remove(x)}$ operations in the YFastTrie results in an $ \mathtt{add(x)}$ or $ \mathtt{remove(x)}$ operation in $ \mathtt{xft}$. By doing this, the average cost incurred by calls to $ \mathtt{xft}$'s $ \mathtt{add(x)}$ and $ \mathtt{remove(x)}$ operations is only constant.

The obvious question becomes: If $ \mathtt{xft}$ only stores $ \mathtt{n}$/ $ \mathtt{w}$ elements, where do the remaining $ \ensuremath{\mathtt{n}}(1-1/\ensuremath{\mathtt{w}})$ elements go? These elements go into secondary structures, in this case an extended version of treaps (Section 7.2). There are roughly $ \mathtt{n}$/ $ \mathtt{w}$ of these secondary structures so, on average, each of them stores $ O(\ensuremath{\mathtt{w}})$ items. Treaps support logarithmic time SSet operations, so the operations on these treaps will run in $ O(\log \ensuremath{\mathtt{w}})$ time, as required.

More concretely, a YFastTrie contains an XFastTrie, $ \mathtt{xft}$, that contains a random sample of the data, where each element appears in the sample independently with probability $ 1/\ensuremath{\mathtt{w}}$. For convenience, the value $ 2^{\ensuremath{\mathtt{w}}}-1$, is always contained in $ \mathtt{xft}$. Let $ \ensuremath{\mathtt{x}}_0<\ensuremath{\mathtt{x}}_1<\cdots<\ensuremath{\mathtt{x}}_{k-1}$ denote the elements stored in $ \mathtt{xft}$. Associated with each element, $ \ensuremath{\mathtt{x}}_i$, is a treap, $ \ensuremath{\mathtt{t}}_i$, that stores all values in the range $ \ensuremath{\mathtt{x}}_{i-1}+1,\ldots,\ensuremath{\mathtt{x}}_i$. This is illustrated in Figure 13.7.

Figure 13.7: A YFastTrie containing the values 0, 1, 3, 4, 6, 8, 9, 10, 11, and 13.
\includegraphics{figs/yfast}

The $ \mathtt{find(x)}$ operation in a YFastTrie is fairly easy. We search for $ \mathtt{x}$ in $ \mathtt{xft}$ and find some value $ \ensuremath{\mathtt{x}}_i$ associated with the treap $ \ensuremath{\mathtt{t}}_i$. When then use the treap $ \mathtt{find(x)}$ method on $ \ensuremath{\mathtt{t}}_i$ to answer the query. The entire method is a one-liner:

    T find(T x) {
        return xft.find(new Pair<T>(it.intValue(x))).t.find(x);
    }
The first $ \mathtt{find(x)}$ operation (on $ \mathtt{xft}$) takes $ O(\log \ensuremath{\mathtt{w}})$ time. The second $ \mathtt{find(x)}$ operation (on a treap) takes $ O(\log r)$ time, where $ r$ is the size of the treap. Later in this section, we will show that the expected size of the treap is $ O(\ensuremath{\mathtt{w}})$ so that this operation takes $ O(\log \ensuremath{\mathtt{w}})$ time.1

Adding an element to a YFastTrie is also fairly simple--most of the time. The $ \mathtt{add(x)}$ method calls $ \mathtt{xft.find(x)}$ to locate the treap, $ \mathtt{t}$, into which $ \mathtt{x}$ should be inserted. It then calls $ \mathtt{t.add(x)}$ to add $ \mathtt{x}$ to $ \mathtt{t}$. At this point, it tosses a biased coin, that comes up heads with probability $ 1/\ensuremath{\mathtt{w}}$. If this coin comes up heads, $ \mathtt{x}$ will be added to $ \mathtt{xft}$.

This is where things get a little more complicated. When $ \mathtt{x}$ is added to $ \mathtt{xft}$, the treap $ \mathtt{t}$ needs to be split into two treaps $ \mathtt{t1}$ and $ \mathtt{t'}$. The treap $ \mathtt{t1}$ contains all the values less than or equal to $ \mathtt{x}$; $ \mathtt{t'}$ is the original treap, $ \mathtt{t}$, with the elements of $ \mathtt{t1}$ removed. Once this is done we add the pair $ \mathtt{(x,t1)}$ to $ \mathtt{xft}$. Figure 13.8 shows an example.

    boolean add(T x) {
        int ix = it.intValue(x);
        STreap<T> t = xft.find(new Pair<T>(ix)).t;
        if (t.add(x)) {
            n++;
            if (rand.nextInt(w) == 0) {
                STreap<T> t1 = t.split(x);
                xft.add(new Pair<T>(ix, t1));
            }
            return true;
        } 
        return false;
    }
Figure 13.8: Adding the values 2 and 6 to a YFastTrie. The coin toss for 6 came up heads, so 6 was added to $ \mathtt{xft}$ and the treap containing $ 4,5,6,8,9$ was split.
\includegraphics{figs/yfast-add}
Adding $ \mathtt{x}$ to $ \mathtt{t}$ takes $ O(\log \ensuremath{\mathtt{w}})$ time. Exercise 7.5 shows that splitting $ \mathtt{t}$ into $ \mathtt{t1}$ and $ \mathtt{t'}$ can also be done in $ O(\log \ensuremath{\mathtt{w}})$ expected time. Adding the pair ( $ \mathtt{x}$, $ \mathtt{t1}$) to $ \mathtt{xft}$ takes $ O(\ensuremath{\mathtt{w}})$ time, but only happens with probability $ 1/\ensuremath{\mathtt{w}}$. Therefore, the expected running time of the $ \mathtt{add(x)}$ operation is

$\displaystyle O(\log\ensuremath{\mathtt{w}}) + \frac{1}{\ensuremath{\mathtt{w}}}O(\ensuremath{\mathtt{w}}) = O(\log \ensuremath{\mathtt{w}})
$

The $ \mathtt{remove(x)}$ method just undoes the work performed by $ \mathtt{add(x)}$. We use $ \mathtt{xft}$ to find the leaf, $ \mathtt{u}$, in $ \mathtt{xft}$ that contains the answer to $ \mathtt{xft.find(x)}$. From $ \mathtt{u}$, we get the treap, $ \mathtt{t}$, containing $ \mathtt{x}$ and remove $ \mathtt{x}$ from $ \mathtt{t}$. If $ \mathtt{x}$ was also stored in $ \mathtt{xft}$ (and $ \mathtt{x}$ is not equal to $ 2^{\ensuremath{\mathtt{w}}}-1$) then we remove $ \mathtt{x}$ from $ \mathtt{xft}$ and add the elements from $ \mathtt{x}$'s treap to the treap, $ \mathtt{t2}$, that is stored by $ \mathtt{u}$'s successor in the linked list. This is illustrated in Figure 13.9.

    boolean remove(T x) {
        int ix = it.intValue(x);
        Node<T> u = xft.findNode(ix);
        boolean ret = u.x.t.remove(x);
        if (ret) n--;
        if (u.x.x == ix && ix != 0xffffffff) {
            STreap<T> t2 = u.child[1].x.t;
            t2.absorb(u.x.t);
            xft.remove(u.x);
        }
        return ret;
    }
Figure 13.9: Removing the values 1 and 9 from a YFastTrie in Figure 13.8.
\includegraphics{figs/yfast-remove}
Finding the node $ \mathtt{u}$ in $ \mathtt{xft}$ takes $ O(\log \ensuremath{\mathtt{w}})$ expected time. Removing $ \mathtt{x}$ from $ \mathtt{t}$ takes $ O(\log \ensuremath{\mathtt{w}})$ expected time. Again, Exercise 7.5 shows that merging all the elements of $ \mathtt{t}$ into $ \mathtt{t2}$ can be done in $ O(\log \ensuremath{\mathtt{w}})$ time. If necessary, removing $ \mathtt{x}$ from $ \mathtt{xft}$ takes $ O(\ensuremath{\mathtt{w}})$ time, but $ \mathtt{x}$ is only contained in $ \mathtt{xft}$ with probability $ 1/\ensuremath{\mathtt{w}}$. Therefore, the expected time to remove an element from a YFastTrie is $ O(\log \ensuremath{\mathtt{w}})$.

Earlier in the discussion, we put off arguing about the sizes of treaps in this structure until later. Before finishing we prove the result we need.

Lemma 13..1   Let $ \mathtt{x}$ be an integer stored in a YFastTrie and let $ \ensuremath{\mathtt{n}}_\ensuremath{\mathtt{x}}$ denote the number of elements in the treap, $ \mathtt{t}$, that contains $ \mathtt{x}$. Then $ \mathrm{E}[\ensuremath{\mathtt{n}}_\ensuremath{\mathtt{x}}] \le 2\ensuremath{\mathtt{w}}-1$.

Proof. Refer to Figure 13.10. Let $ \ensuremath{\mathtt{x}}_1<\ensuremath{\mathtt{x}}_2<\cdots<\ensuremath{\mathtt...
...=\ensuremath{\mathtt{x}}<\cdots<\ensuremath{\mathtt{x}}_\ensuremath{\mathtt{n}}$ denote the elements stored in the YFastTrie. The treap $ \mathtt{t}$ contains some elements greater than or equal to $ \mathtt{x}$. These are $ \ensuremath{\mathtt{x}}_i,\ensuremath{\mathtt{x}}_{i+1},\ldots,\ensuremath{\mathtt{x}}_{i+j-1}$, where $ \ensuremath{\mathtt{x}}_{i+j-1}$ is the only one of these elements in which the biased coin toss performed in the $ \mathtt{add(x)}$ method came up heads. In other words, $ \mathrm{E}[j]$ is equal to the expected number of biased coin tosses required to obtain the first heads.2 Each coin toss is independent and comes up heads with probability $ 1/\ensuremath{\mathtt{w}}$, so $ \mathrm{E}[j]\le\ensuremath{\mathtt{w}}$. (See Lemma 4.2 for an analysis of this for the case $ \ensuremath{\mathtt{w}}=2$.)

Similarly, the elements of $ \mathtt{t}$ smaller than $ \mathtt{x}$ are $ \ensuremath{\mathtt{x}}_{i-1},\ldots,\ensuremath{\mathtt{x}}_{i-k}$ where all these $ k$ coin tosses come up tails and the coin toss for $ \ensuremath{\mathtt{x}}_{i-k-1}$ comes up heads. Therefore, $ \mathrm{E}[k]\le\ensuremath{\mathtt{w}}-1$, since this is the same coin tossing experiment considered previously, but in which the last toss doesn't count. In summary, $ \ensuremath{\mathtt{n}}_\ensuremath{\mathtt{x}}=j+k$, so

$\displaystyle \mathrm{E}[\ensuremath{\mathtt{n}}_\ensuremath{\mathtt{x}}] = \ma...
...athrm{E}[j] + \mathrm{E}[k] \le 2\ensuremath{\mathtt{w}}-1 \enspace . \qedhere $

$ \qedsymbol$

Figure 13.10: The number of elements in the treap, $ \mathtt{t}$, containing $ \mathtt{x}$ is determined by two coin tossing experiments.
\includegraphics{figs/yfast-sample}

Lemma 13.1 was the last piece in the proof of the following theorem, which summarizes the performance of the YFastTrie:

Theorem 13..3   A YFastTrie implements the SSet interface for $ \mathtt{w}$-bit integers. A YFastTrie supports the operations $ \mathtt{add(x)}$, $ \mathtt{remove(x)}$, and $ \mathtt{find(x)}$ in $ O(\log \ensuremath{\mathtt{w}})$ time per operation. The space used by a YFastTrie that stores $ \mathtt{n}$ values is $ O(\ensuremath{\mathtt{n}}+\ensuremath{\mathtt{w}})$.

The $ \mathtt{w}$ term in the space requirement comes from the fact that $ \mathtt{xft}$ always stores the value $ 2^\ensuremath{\mathtt{w}}-1$. The implementation could be modified (at the expense of adding some extra cases to the code) so that it is unnecessary to store this value. In this case, the space requirement in the theorem becomes $ O(\ensuremath{\mathtt{n}})$.



Footnotes

... time.1
This is an application of Jensen's Inequality: If $ \mathrm{E}[r]=\ensuremath{\mathtt{w}}$, then $ \mathrm{E}[\log r]
\le \log w$.
... heads.2
This analysis ignores the fact that $ j$ never exceeds $ \ensuremath{\mathtt{n}}-i+1$. However, this only decreases $ \mathrm{E}[j]$, so the upper bound still holds
opendatastructures.org