Achieving Optimal Redundancy for Small Dynamic Rank/Select Dictionaries
En palabras de los autores
In this paper, we study the number of bits required to construct a dynamic dictionary with optimal time for operations. Using the standard (multiplication) Word-RAM model with -bit words, we construct a data-structure for a dynamic dictionary for a set of elements that, given a parameter , uses taking optimal time (worst-case) for all operations. We show optimality for by extending the lower bound of Li, Liang, Yu, and Zhou [FOCS 2023] to super-polynomial universes: any dynamic dictionary for elements that uses bits requires time for operations. Lastly, we extend the data-structure to a dynamic fully indexable dictionary (that also supports on the complement of ).
Apareció: viernes, 2 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 18 pages; 2 figures