Operators over Compressed Integer Encodings

Compact representation of integer values is a key feature for data compression. A compressed representation allows us to store more integers within less space, and therefore, to work in faster hierarchies of memory. Adaptive searching yields to compressed representations of integers. In scenarios where the cost of updating the encoding is high, approaches to perform operations over integers dynamically are preferable. In this paper we present a framework to create integer encodings, based on augmenting search algorithms in the comparison model. We show that such algorithms share common properties allowing the support of arithmetic and logic operations over the encoded integers. Finally, we propose a practical approach to support these operations over Elias integer encodings.