Succinct Dynamic Ordered Sets with Random Access
share
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 compressed space regime is the problem we address in this work. For a polynomial universe m = n^Θ(1), we give a solution that takes EF(n,m) + o(n) bits, where EF(n,m) ≤ nlog_2(m/n) + 2n is the cost in bits of the Elias-Fano representation of the set, and supports random access to the i-th smallest element in O(log n/ loglog n) time, updates and predecessor search in O(loglog n) time. These time bounds are optimal.
READ FULL TEXT