ETD

• bitpacking
• compression
• Ebay
• forward index
• lightweight compression

This thesis investigates how lightweight block-based compression, and compression in general, can be leveraged to improve random access on sequences of integers. In particular, the concepts were applied in the context of forward indexes, which perfectly fit the use case. Different types of random access were required for the implementation, including complete random access, monotonic access, full traversal, and full decompression of the encoded vector.In particular monotonic access was the one required to perform best. This drove to a specific implementation to maximize access speed with queries with increasing accesses. Compression was included in this work because the main focus was on re-ducing memory consumption and improving access times.

The final implementation consists in an hybrid index, which uses both columnar and row storing, in order to leverage the advantages of both.