RECORD
Small Uncolored and Colored Choice Dictionaries
Data Structures and Algorithms · Submitted 20 Sep 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We describe a new choice dictionary that executes all operations in constant time and, in addition to the space needed to store the integer $n$, occupies only $n+1$ bits, which is shown to be optimal if $w=o(n)$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
A choice dictionary can be initialized with a parameter $n\in\mathbb{N}$ and subsequently maintains an initially empty subset $S$ of $\{1,\ldots,n\}$ under insertion, deletion, membership queries and an operation $\textit{choice}$ that returns an arbitrary element of $S$. The choice dictionary is fundamental in space-efficient computing and has numerous applications. The best previous choice dictionary can be initialized with $n$ and $t\in\mathbb{N}$ and subsequently executes all operations in $O(t)$ time and occupies $n+O(n({t/w})^t+\log n)$ bits on a word RAM with a word length of $w=\Omega(\log n)$ bits. We describe a new choice dictionary that executes all operations in constant time and, in addition to the space needed to store the integer $n$, occupies only $n+1$ bits, which is shown to be optimal if $w=o(n)$. A generalization of the choice dictionary called a colored choice dictionary is initialized with $c\in\mathbb{N}$ in addition to $n$ and subsequently maintains a semipartition $(S_0,\ldots,S_{c-1})$ of $\{1,\ldots,n\}$ under the operations $\textit{setcolor}(j,\ell)$, which moves $\ell$ from its current subset to $S_j$, $\textit{color}(\ell)$, which returns the unique $j\in\{0,\ldots,c-1\}$ with $\ell\in S_j$, and $\textit{choice}(j)$, which returns an arbitrary element of $S_j$. We describe new colored choice dictionaries that, if initialized with constant $c$, execute $\textit{setcolor}$, $\textit{color}$ and $\textit{choice}$ in constant time and occupy $n\log_2\!c+1$ bits plus the space needed to store $n$ if $c$ is a power of 2, and at most $n\log_2\!c+n^\epsilon$ bits in general, for arbitrary fixed $\epsilon>0$. We also study the possibility of iterating over the set $S$ or over $S_j$ for given $j\in\{0,\ldots,c-1\}$ and an application of this to breadth-first search.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A choice dictionary can be initialized with a parameter $n\in\mathbb{N}$ and subsequently maintains an initially empty subset $S$ of $\{1,\ldots,n\}$ under insertion, deletion, membership queries and an operation $\textit{choice}$ that returns an arbitrary element of $S$. | background 1.00 | 0.11 | 0.03 | asserted 0.99 |
| s1 | The choice dictionary is fundamental in space-efficient computing and has numerous applications. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s2 | The best previous choice dictionary can be initialized with $n$ and $t\in\mathbb{N}$ and subsequently executes all operations in $O(t)$ time and occupies $n+O(n({t/w})^t+\log n)$ bits on a word RAM with a word length of $w=\Omega(\log n)$ bits. | background 0.96 | 0.03 | 0.03 | asserted 1.00 |
| s3 | We describe a new choice dictionary that executes all operations in constant time and, in addition to the space needed to store the integer $n$, occupies only $n+1$ bits, which is shown to be optimal if $w=o(n)$. | contribution 0.65 | 0.97 | 0.80 | asserted 1.00 |
| s4 | A generalization of the choice dictionary called a colored choice dictionary is initialized with $c\in\mathbb{N}$ in addition to $n$ and subsequently maintains a semipartition $(S_0,\ldots,S_{c-1})$ of $\{1,\ldots,n\}$ under the operations $\textit{setcolor}(j,\ell)$, which moves $\ell$ from its current subset to $S_j$, $\textit{color}(\ell)$, which returns the unique $j\in\{0,\ldots,c-1\}$ with $\ell\in S_j$, and $\textit{choice}(j)$, which returns an arbitrary element of $S_j$. | background 0.65 | 0.20 | 0.04 | asserted 0.99 |
| s5 | We describe new colored choice dictionaries that, if initialized with constant $c$, execute $\textit{setcolor}$, $\textit{color}$ and $\textit{choice}$ in constant time and occupy $n\log_2\!c+1$ bits plus the space needed to store $n$ if $c$ is a power of 2, and at most $n\log_2\!c+n^\epsilon$ bits in general, for arbitrary fixed $\epsilon>0$. | contribution 0.57 | 0.97 | 0.17 | asserted 1.00 |
| s6 | We also study the possibility of iterating over the set $S$ or over $S_j$ for given $j\in\{0,\ldots,c-1\}$ and an application of this to breadth-first search. | contribution 0.96 | 0.84 | 0.03 | hedged possibility 0.53 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
A choice dictionary can be initialized with a parameter $n\in\mathbb{N}$ and subsequently maintains an initially empty subset $S$ of $\{1,\ldots,n\}$ under insertion, deletion, membership queries and an operation $\textit{choice}$ that returns an arbitrary element of $S$. The choice dictionary is fundamental in space-efficient computing and has numerous applications. The best previous choice dictionary can be initialized with $n$ and $t\in\mathbb{N}$ and subsequently executes all operations in $O(t)$ time and occupies $n+O(n({t/w})^t+\log n)$ bits on a word RAM with a word length of $w=\Omega(\log n)$ bits. We describe a new choice dictionary that executes all operations in constant time and, in addition to the space needed to store the integer $n$, occupies only $n+1$ bits, which is shown to be optimal if $w=o(n)$. A generalization of the choice dictionary called a colored choice dictionary is initialized with $c\in\mathbb{N}$ in addition to $n$ and subsequently maintains a semipartition $(S_0,\ldots,S_{c-1})$ of $\{1,\ldots,n\}$ under the operations $\textit{setcolor}(j,\ell)$, which moves $\ell$ from its current subset to $S_j$, $\textit{color}(\ell)$, which returns the unique $j\in\{0,\ldots,c-1\}$ with $\ell\in S_j$, and $\textit{choice}(j)$, which returns an arbitrary element of $S_j$. We describe new colored choice dictionaries that, if initialized with constant $c$, execute $\textit{setcolor}$, $\textit{color}$ and $\textit{choice}$ in constant time and occupy $n\log_2\!c+1$ bits plus the space needed to store $n$ if $c$ is a power of 2, and at most $n\log_2\!c+n^\epsilon$ bits in general, for arbitrary fixed $\epsilon>0$. We also study the possibility of iterating over the set $S$ or over $S_j$ for given $j\in\{0,\ldots,c-1\}$ and an application of this to breadth-first search.
Human review
How the literature uses it
1 arXiv paper cite this in 3 sentences
Papers citing it
Uses its method or tool 1 paper
-
In the next lemma we use a choice dictionary [ref] that manages a subset $U'$ of a universe $U = {1, …, n}$ and provides—besides constant-time operations contains, add and remove—a linear-time iteration over $U'$.
Space-Efficient Vertex Separators for Treewidth · Iterator for Tree Decompositions using $O(kn)$ bits · 1.00
Cites it as background 1 paper
-
As a solution researchers began to provide space-efficient algorithms and data structures to solve basic problems like graph-connectivity problems [ref] , other graph problems [ref] , memory initialization [ref] , dictionaries with constant-time operations [ref] or graph interfaces [ref] space efficiently, i.e., they designed practical algorithms and data-structures that run (almost) as fast as standard solutions for the problem under consideration while using asymptotically less space.
Space-Efficient Vertex Separators for Treewidth · Introduction · 0.96
What it cites · 11 sentences without a confident label
Uses the method or tool of 2 papers
-
Our new results were obtained by combining techniques of Katoh and Goto [ref] and Hagerup and Kammer [ref] with new ideas.
Succinct Choice Dictionaries · Introduction · 0.93
-
Our new results were obtained by combining techniques of Katoh and Goto [ref] and Hagerup and Kammer [ref] with new ideas.
In-Place Initializable Arrays · Introduction · 0.93
Compares with 1 paper
-
The best previous choice dictionary [ref] can be initialized with a universe size $n$ and a second parameter $t∈$ in constant time and subsequently executes all operations in $O(t)$ time and occupies $n+O(n(t/w)^t+logn)$ bits.
Succinct Choice Dictionaries · Introduction · 0.99
Cites as support 1 paper
-
The optimality of the bound of $n+1$ bits follows from a simple argument of [ref] : Because the client set $S$ of a choice dictionary with universe size $n$ can be in $2^n$ different states, any two of which can be distinguished via calls of $contains$, if the choice dictionary uses only $n$ bits it must represent each possible state of $S$ through a unique bit pattern.
In-Place Initializable Arrays · Introduction · 0.98
Cites as background 1 paper
-
Following similar earlier definitions [ref] and concurrently with that of [ref] , the choice-dictionary data type was introduced by Hagerup and Kammer [ref] as a basic tool in space-efficient computing and is known to have numerous applications [ref] .
Succinct Choice Dictionaries · Introduction · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.