Lawrence Berkeley National Laboratory

This paper presents a systematic study of two large subsets of bitmap indexing methods that use multi-component and multi-level encodings. Earlier studies on bitmap indexes are either empirical or for uncompressed versions only. Since most of bitmap indexes in use are compressed, we set out to study the performance characteristics of these compressed indexes. To make the analyses manageable, we choose to use a particularly simple, but efficient, compression method called the Word-Aligned Hybrid (WAH) code. Using this compression method, a number of bitmap indexes are shown to be optimal because their worst-case time complexities for answering a query is a linear function of the number of hits. Since compressed bitmap indexes behave drastically different from uncompressed ones, our analyses also lead to a number of new methods that are much more efficient than commonly used ones. As a validation for the analyses, we implement a number of the best methods and measure their performance against well-known indexes. The fastest new methods are predicted and observed to be 5 to 10 times faster than well-known indexing methods.