Papers for

compression engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Compact dictionaries enable fast updates and queries with minimal extra space

Achieving Optimal Redundancy for Small Dynamic Rank/Select Dictionaries

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$).

Thu 1 OctData Structures and Algorithms
The gist
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.
Open → 2610.01853v1