Please use this identifier to cite or link to this item:
|Title:||Compact Dynamic Rewriteable (CDRW) Arrays|
Puglisi, S. J.
|Presented at:||ACM-SIAM Meeting on Algorithm Engineering and Experiments (ALENEX17) Barcelona, Spain|
|Publisher:||Society for Industrial and Applied Mathematics (SIAM)|
|Citation:||Proceedings of the ACM-SIAM meeting on Algorithm Engineering and Experiments (ALENEX17), pp. ?-? (11)|
|Abstract:||In 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.|
|Embargo on file until:||1-Jan-10000|
|Rights:||Copyright © 2017, Society for Industrial and Applied Mathematics (SIAM). Deposited with reference to the publisher’s open access archiving policy.|
|Description:||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.|
|Appears in Collections:||Conference Papers & Presentations, Dept. of Computer Science|
Files in This Item:
|cdrw.pdf||Post-review (final submitted author manuscript)||421.07 kB||Unknown||View/Open|
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.