Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes

Owen Kaser, Daniel Lemire, Kamel Aouiche

Bitmap indexes must be compressed to reduce input/output costs and minimize CPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we use techniques based on run-…