Compressing Dynamic Fully Indexable Dictionaries in Word-RAM

We study the problem of constructing a dynamic fully indexable dictionary (FID) in the Word-RAM model using space close to the information-theoretic lower bound. A FID is a data-structure that encodes a bit-vector B of length u and answers, for b∈0,1, rankb(B, x)=|y≤ x | B[y]=b| and selectb(B, r)=min0≤ x<u | rankb(B, x)=r (−1 if empty). A dynamic FID supports updates that modify a single bit of B, i.e., B[i]← b. We work in the Word-RAM model with w-bit words, assuming w≥ lg u. Integer multiplication takes O(1) time. Our memory model is MB, allowing access to a fixed precomputed table of τ=polylog(w) words, which can be computed in O(wτ) time. In this paper, we show a dynamic FID based on the famous fusion-tree data-structure of Pătraşcu and Thorup [FOCS 2014], modified to use fewer bits and to support select0. Let n denote the number of ones in B. We describe a parametric construction: for every є≤ 1/2, there is a dynamic FID using lg⎛ ⎜ ⎝un⎞ ⎟ ⎠+O(nwє/є) bits taking O(1/є+logw(n)) time for rank0/rank1/select0 and updates, and O(logw(n)) time for select1. All time bounds are worst-case. For є=1/√lg w, we reduce the space to lg(un)+O(nlogw) bits. For є=Θ(1), the running time matches the lower bound of Fredman and Saks [STOC 1989]. For є=1/4, this is the first deterministic dynamic FID using multiplication that achieves o(n√w) bits of redundancy in MB, and optimal worst-case time.