RECORD
On-the-Fly Array Initialization in Less Space
Data Structures and Algorithms · Submitted 29 Sep 2017
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that for all given $n,t,w \in \{1,2,...\}$ with $n<2^w$, an array of $n$ entries of $w$ bits each can be represented on a word RAM with a word length of $w$ bits in at most $nw+\lceil n(t/(2 w))^t\rceil$ bits of uninitialized memory to support constant-time initialization of the whole array and $O(t)$-time reading and writing of individual array entries.
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
We show that for all given $n,t,w \in \{1,2,...\}$ with $n<2^w$, an array of $n$ entries of $w$ bits each can be represented on a word RAM with a word length of $w$ bits in at most $nw+\lceil n(t/(2 w))^t\rceil$ bits of uninitialized memory to support constant-time initialization of the whole array and $O(t)$-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with $nw+\lceil n/w^t\rceil$ bits for arbitrary fixed $t$, to be compared with $nw+\Theta(n)$ bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support $O(\log n)$-time access with just $nw+1$ bits, which is optimal for arbitrary access times if the initialization executes fewer than $n$ steps.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We show that for all given $n,t,w \in \{1,2,...\}$ with $n<2^w$, an array of $n$ entries of $w$ bits each can be represented on a word RAM with a word length of $w$ bits in at most $nw+\lceil n(t/(2 w))^t\rceil$ bits of uninitialized memory to support constant-time initialization of the whole array and $O(t)$-time reading and writing of individual array entries. | result 0.71 | 0.94 | 0.81 | asserted 1.00 |
| s1 | At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with $nw+\lceil n/w^t\rceil$ bits for arbitrary fixed $t$, to be compared with $nw+\Theta(n)$ bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support $O(\log n)$-time access with just $nw+1$ bits, which is optimal for arbitrary access times if the initialization executes fewer than $n$ steps. | result 0.78 | 0.91 | 0.38 | asserted 1.00 |
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
We show that for all given $n,t,w \in \{1,2,...\}$ with $n<2^w$, an array of $n$ entries of $w$ bits each can be represented on a word RAM with a word length of $w$ bits in at most $nw+\lceil n(t/(2 w))^t\rceil$ bits of uninitialized memory to support constant-time initialization of the whole array and $O(t)$-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with $nw+\lceil n/w^t\rceil$ bits for arbitrary fixed $t$, to be compared with $nw+\Theta(n)$ bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support $O(\log n)$-time access with just $nw+1$ bits, which is optimal for arbitrary access times if the initialization executes fewer than $n$ steps.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 3 sentences without a confident label
Compares with 1 paper
-
Very recently, giving a clever twist to the folklore method, Katoh and Goto [ref] devised a clearable word array that executes every operation in constant time but, when the universe size is $n$, uses just $n w+1$ bits.
In-Place Initializable Arrays · Our Contribution · 0.95
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.