Please use this identifier to cite or link to this item:
Title: Compact Dynamic Rewriteable (CDRW) Arrays
Authors: Poyias, A.
Puglisi, S. J.
Raman, Rajeev
First Published: 18-Jan-2017
Presented at: ACM-SIAM Meeting on Algorithm Engineering and Experiments (ALENEX17) Barcelona, Spain
Start Date: 17-Jan-2017
End Date: 18-Jan-2017
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.
DOI Link: 10.1137/1.9781611974768.9
Embargo on file until: 1-Jan-10000
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
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:
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.