dc.contributor.author | Gupta, Ankur | |
dc.contributor.author | Hon, Wing-Kai | |
dc.contributor.author | Shah, Rahul | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-21T19:54:14Z | |
dc.date.available | 2011-03-21T19:54:14Z | |
dc.date.issued | 2007-11-22 | |
dc.identifier.citation | A. Gupta, W.-K. Hon, R. Shah, and J. S. Vitter. “Compressed Data Structures: Dictionaries and the Data-Aware Measures,” Theoretical Computer Science, 387(3), November 2007, 313–331. An extended abstract appears in Proceedings of the 2006 IEEE Data Compression Conference (DCC ’06), Snowbird, UT, March 2006, 213–222. | |
dc.identifier.uri | http://hdl.handle.net/1808/7222 | |
dc.description.abstract | We propose measures for compressed data structures, in which space usage is mea-
sured in a data-aware manner. In particular, we consider the fundamental dictionary problem
on set data, where the task is to construct a data structure to represent a set S of n items
out of a universe U = f0; : : : ; u 1g and support various queries on S. We use a well-known
data-aware measure for set data called gap to bound the space of our data structures.
We describe a novel dictionary structure taking gap+O(n log(u=n)= log n)+O(n log log(u=n))
bits. Under the RAM model, our dictionary supports membership, rank, select, and prede-
cessor queries in nearly optimal time, matching the time bound of Andersson and Thorup's
predecessor structure [AT00], while simultaneously improving upon their space usage. Our
dictionary structure uses exactly gap bits in the leading term (i.e., the constant factor is 1)
and answers queries in near-optimal time. When seen from the worst case perspective, we
present the rst O(n log(u=n))-bit dictionary structure which supports these queries in near-
optimal time under RAM model. We also build a dictionary which requires the same space
and supports membership, select, and partial rank queries even more quickly in O(log log n)
time. To the best of our knowledge, this is the rst of a kind result which achieves data-aware
space usage and retains near-optimal time. | |
dc.language.iso | en_US | |
dc.publisher | Elsevier | |
dc.title | Compressed Data Structures: Dictionaries and the Data-Aware Measures | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1016/j.tcs.2007.07.042 | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |