An Improved Bitmap Index Compression Scheme

Abstract

Bitmap indexes are commonly used in most data warehousing applications such as on-line analytical processing. By storing the bitmaps in compressed form, these have been shown to be efficient 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 thesis, we propose a new scheme called Super Byte-aligned Hybrid (SBH) bitmap compression. It is byte-based scheme that helps to reduce the space and uses the bucket to speed up the query processing time. The query processing time of SBH is up to five times faster than that of WAH, while the size of compressed bitmap indexes is retained nearly close to that of BBC. Thus, our scheme improves upon both these schemes. In addition, we implemented a data structure that combines B-tree and bitmap indexes. The performance of the data structure is evaluated by comparing with the Multi-resolution bitmap indexes, and we confirm the efficiency of the data structure.