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)
Published in
Proceedings of the ACM-SIAM meeting on Algorithm Engineering and Experiments (ALENEX17)Publisher
Society for Industrial and Applied Mathematics (SIAM)isbn
978-1-61197-476-8Acceptance date
2016-11-02Copyright date
2017Publisher DOI
Publisher version
http://epubs.siam.org/doi/abs/10.1137/1.9781611974768.9Notes
The file associated with this record is under embargo while permission to archive is sought from the publisher. The full text may be available through the publisher links provided above.Temporal coverage: start date
2017-01-17Temporal coverage: end date
2017-01-18Language
enAdministrator link
Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC