Compressed bitmap indices for efficient query processing

Kesheng Wu, Ekow J. Otoo and Arie Shoshani


Bitmap indices are useful techniques for improving access speed of high-dimensional data in data warehouses and in large scientific databases. Even though the bitmaps are easy to compress, compressing them can significantly reduce the query processing efficiency. This is because the operations on the compressed bitmaps are much slower than the same operations on the uncompressed ones. To address this problem, we developed a new word-aligned compression scheme that uses a little more space, but is much faster than earlier methods. Using this compression technique, we evaluate several bitmap encoding schemes, including the equality encoding, the range encoding and the interval encoding. In our tests, the compressed bitmap indices are not only much smaller in size than their uncompressed versions, but are also just as fast in query processing as their uncompressed counterparts. In these tests, the compressed bitmap indices using different encoding schemes show different space and time trade-offs. To search for more useful choices, we also present several two-level schemes.

full text of LBNL-47807 (PDF)

More research work by John Wu
Bitmap Index
Connected Component Labeling
Eigenvalue Computation
Inforamtion available elsewhere on the web
Google Scholar
Contact us

John Wu