Title

Variable Word Length Word-Aligned Hybrid Compression (Short Paper)

Authors

Florian Grieskamp, Roland Kühn, and Jens Teubner

Published

16th Int'l Workshop on Data Management on New Hardware (DaMoN), Portland, OR, USA, June 2020

Abstract

The Word-Aligned Hybrid (WAH) compression is a prominent example of a lightweight compression scheme for bitmap indices that
considers the word size of the underlying architecture. This is a compromise toward commodity CPUs, where operations below the
word granularity perform poorly. With the emergence of novel hardware classes, such compromises may no longer be appropriate.
Field-programmable gate arrays (FPGAs) do not even have any meaningful “word size”.
In this work, we reconsider strategies for bitmap compression in the light of modern hardware architectures. Rather than tuning
compression toward a fixed word size, we propose to tune the word size toward optimal compression. The resulting compression
scheme, Variable Word Length Word-Aligned Hybrid (VWLWAH), improves compression rates by almost 75 % while maintaining line
rate performance on FPGAs.

Projects

Real-Time Analysis and Storage of High-Volume Data in Particle Physics (SFB 876, C5)

Publication Log

May 2020

• camera-ready paper

March 2020

Submission to DaMoN 2020 (result: accepted as short paper)

• submission (PDF)
• reviews (reject, accept, reject)