Succinct Dynamic Ordered Sets with Random Access

Abstract

The representation of a dynamic ordered set of $n$ integer keys drawn from a universe of size $m$ is a fundamental data structuring problem. Many solutions to this problem achieve optimal time but take polynomial space, therefore preserving time optimality in the \emph{compressed} space regime is the problem we address in this work. For a polynomial universe $m=n^{\Theta (1)}$, we give a solution that takes $\text{EF}(n,m)+o(n)$ bits, where $\text{EF}(n,m)\le n\lceil {\log }_2(m/n)\rceil +2n$ is the cost in bits of the \emph{Elias-Fano} representation of the set, and supports random access to the $i$-th smallest element in $O(\log n/\log \log n)$ time, updates and predecessor search in $O(\log \log n)$ time. These time bounds are optimal.