SBH: Super byte-aligned hybrid bitmap compression

• The paper proposes a version of a compressed bitmap indexing scheme called Super Byte-aligned Hybrid (SBH).
• It improves upon two of the well-known and most widely used compressed bitmap indexes called BBC and WAH.
• The query processing time of SBH is five times faster than that of WAH, while the size of compressed bitmap indexes is retained nearly close to that of BBC.
• The performance of our scheme gets better for cardinalities larger than 50 when compared to other schemes.

Bitmap indexes are commonly used in data warehousing applications such as on-line analytic processing (OLAP). Storing the bitmaps in compressed form has been shown to be effective not only for low cardinality attributes, as conventional wisdom would suggest, but also for high cardinality attributes. Compressed bitmap indexes, such as Byte-aligned Bitmap Compression (BBC), Word-Aligned Hybrid (WAH) and several of their variants have been shown to be efficient in terms of both time and space, compared to traditional database indexes. In this paper, we propose a new technique for compressed bitmap indexing, called Super Byte-aligned Hybrid (SBH) bitmap compression, which improves upon the current state-of-the-art compression schemes. In our empirical evaluation, the query processing time of SBH was about five times faster than that of WAH, while the size of its compressed bitmap indexes was retained nearly close to that of BBC.