Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPoyias, A.-
dc.contributor.authorPuglisi, S. J.-
dc.contributor.authorRaman, Rajeev-
dc.identifier.citationProceedings of the ACM-SIAM meeting on Algorithm Engineering and Experiments (ALENEX17), pp. ?-? (11)en
dc.descriptionThe 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.-
dc.description.abstractIn 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.en
dc.description.sponsorshipThe work is partially suported by the Academy of Finland through grant 294143.en
dc.publisherSociety for Industrial and Applied Mathematics (SIAM)en
dc.rightsCopyright © 2017, Society for Industrial and Applied Mathematics (SIAM). Deposited with reference to the publisher’s open access archiving policy.en
dc.titleCompact Dynamic Rewriteable (CDRW) Arraysen
dc.typeConference Paperen
dc.description.presentedACM-SIAM Meeting on Algorithm Engineering and Experiments (ALENEX17) Barcelona, Spainen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERINGen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Scienceen
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
cdrw.pdfPost-review (final submitted author manuscript)421.07 kBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.