Compact dictionaries enable fast updates and queries with minimal extra space

Achieving Optimal Redundancy for Small Dynamic Rank/Select Dictionaries

Data Structures and Algorithms

Summary

This paper looks at how to build dynamic dictionaries—data structures that store sets of numbers—that can quickly answer questions like "how many elements are less than this number?" or "what is the element at this position?" while using very little extra memory above the theoretical minimum. The authors design a new data structure that balances space and speed, showing it uses nearly the least possible bits and supports quick updates and queries. They also show that their trade-off between memory use and operation speed is essentially the best anyone can do for reasonably sized sets. Finally, they extend their method to handle queries about elements not in the set as well.

What this means in practice

  • For database developers: Implement highly space-efficient indexes that support fast membership, rank, and select queries for dynamic large-scale data collections.
  • For compression engineers: Optimize compressed data representations that require supporting quick updates and queries with minimal storage overhead.

A theory result. No direct application yet.

Authors

Gabriel Marques Domingues

Abstract

In this paper, we study the number of bits required to construct a dynamic dictionary with optimal time for $\texttt{rank}/\texttt{select}$ operations. Using the standard (multiplication) Word-RAM model with $w$-bit words, we construct a data-structure for a dynamic $\texttt{rank}/\texttt{select}$ dictionary for a set $S\subseteq\{0,1,\cdots,u-1\}$ of $n$ elements that, given a parameter $1\leq k\leq \log^*w$, uses $$\operatorname{lg}\binom{u}{n}+\mathcal{O}(n\log^{(k)}w)\text{ bits}$$ taking optimal $\mathcal{O}(k+\log_w n)$ time (worst-case) for all operations. We show optimality for $n=w^{\mathcal{O}(1)}$ by extending the lower bound of Li, Liang, Yu, and Zhou [FOCS 2023] to super-polynomial universes: any dynamic dictionary for $n\leq \sqrt{u}$ elements that uses $\operatorname{lg}\binom{u}{n}+\mathcal{O}(n\log^{(k)}n)$ bits requires $Ω(k)$ time for operations. Lastly, we extend the data-structure to a dynamic fully indexable dictionary (that also supports $\texttt{rank}/\texttt{select}$ on the complement of $S$).
View PDFOpen arXiv