File(s) under permanent embargo
Reason: This item is currently closed access.
Compact Dynamic Rewriteable (CDRW) Arrays
conference contribution
posted on 2016-12-01, 10:12 authored by A. Poyias, S. J. Puglisi, Rajeev RamanIn this paper we consider the problem of compactly representing
a rewritable array of bit-strings. The operations
supported are: create(N, k), which creates a new array of
size N, where each entry is of size at most k bits and equal
to 0; set(i, v), which sets A[i] to v, provided that v is at
most k bits long and get(i) which returns the value of A[i].
Our aim is to approach the minimum possible space bound
of S =
PN−1
i=0 |A[i]|, where |A[i]| ≥ 1 is the length in bits of
the number in A[i], while simultaneously supporting operations
in O(1) time. We call such a data structure a Compact
Dynamic Rewriteable Array (CDRW) array.
On the word RAM model with word size w, for n < 2
w
and k ≤ w, we give practical solutions based on compact
hashing that achieve O(1/ ) expected time for get and set
and use (1 + )S + O(N) bits, for any constant > 0.
Experimental evaluation of our (preliminary, only somewhat
optimized) implementations shows excellent performance in
terms of both space and time, particularly when heuristics
are added to our base algorithms.
Funding
The work is partially suported by the Academy of Finland through grant 294143.
History
Citation
Proceedings of the ACM-SIAM meeting on Algorithm Engineering and Experiments (ALENEX17), pp. ?-? (11)Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer ScienceSource
ACM-SIAM Meeting on Algorithm Engineering and Experiments (ALENEX17) Barcelona, SpainVersion
- AM (Accepted Manuscript)