Cell-Probe Lower Bounds for Succinct Partial Sums

The partial sums problem in succinct data structures asks to preprocess an array A [1 ‥ n ] of bits into a data structure using as close to n bits as possible, and answer queries of the form. The problem has been intensely studied, and features as a subroutine in a number of succinct data structures. We show that, if we answer R ank ( k ) queries by probing t cells of w bits, then the space of the data structure must be at least n + n / w O ( t ) bits. This redundancy/probe trade-off is essentially optimal: Patrascu [FOCS'08] showed how to achieve n + n /( w/t ) Ω( t ) bits. We also extend our lower bound to the closely related Select queries, and to the case of sparse arrays.

Authors

• Mihai Patrascu
• Emanuele Viola

Keywords

No keywords are indexed for this paper.