Compressed data structures: Dictionaries and data-aware measures

In this paper, we propose measures for compressed data structures, in which space usage is measured 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 for representing a set S$S$ of n$n$ items out of a universe U={0,…,u−1}$U=\{0,\dots ,u-1\}$ and supporting various queries on S$S$. We use a well-known data-aware measure for set data called gap to bound the space of our data structures.