论文标题
带随机访问的简洁动态排序集
Succinct Dynamic Ordered Sets with Random Access
论文作者
论文摘要
从大小$ m $的宇宙中绘制的$ n $ integer键的动态有序集的表示是一个基本的数据结构问题。解决此问题的许多解决方案达到了最佳时间，但要使用多项式空间，因此在\ emph {compressed}空间制度中保留时间最佳性是我们在这项工作中解决的问题。对于多项式宇宙$ m = n^{θ（1）} $，我们提供了一个解决方案，该解决方案采用$ \ textsf {ef}（n，m） + o（n） + bits，其中$ \ textsf {ef}（ef}（ef}（n，m） \ emph {elias-fano}的表示，并支持$ o（\ log n/ \ log \ log \ log \ log \ log \ log n）$ time中的$ i $ them元素的随机访问，更新和前任搜索$ o（\ log \ log \ log \ log n）$ time。这些时间范围是最佳的。
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^{Θ(1)}$, we give a solution that takes $\textsf{EF}(n,m) + o(n)$ bits, where $\textsf{EF}(n,m) \leq 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.
