On-the-fly array initialization in less space

DOI10.4230/LIPICS.ISAAC.2017.44MaRDI QIDQ5136264zbMATH OpenOpenAlexFDO

Authors Torben Hagerup, Frank Kammer

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1709.10477

zbMATH Keywords

data structuresarraysspace efficiencyconstant-time initializationon-the-fly initialization

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: We show that for all given $n,t,win1,2,\mathrm{...}$ 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+lceiln(t/(2w){)}^{t}ceil$ 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+lceiln/w^{t}ceil$ 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(logn)$-time access with just $nw+1$ bits, which is optimal for arbitrary access times if the initialization executes fewer than $n$ steps.

Recommendations

• Extra space during initialization of succinct data structures and dynamical initializable arrays
• Compact dynamic rewritable (CDRW) arrays
• scientific article; zbMATH DE number 1830754
• scientific article; zbMATH DE number 2185599
• scientific article; zbMATH DE number 140460

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• An implicit data structure for searching a multikey table in logarithmic time
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• No sorting? Better searching!
• Space-Efficient Euler Partition and Bipartite Edge Coloring
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Surpassing the information theoretic bound with fusion trees

Cited in

(5)

• Extra space during initialization of succinct data structures and dynamical initializable arrays
• In-place initializable arrays
• Space-efficient vertex separators for treewidth
• Compact dynamic rewritable (CDRW) arrays
• Inferring complete initialization of arrays

This page was built for publication: On-the-fly array initialization in less space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136264)