LBNL-48975 Abs.

A Performance Comparison of bitmap indexes

Kesheng Wu, Ekow J. Otoo and Arie Shoshani


We present a comparison of two new word-aligned schemes with some schemes for compressing bitmap indexes, including the well-known byte-aligned bitmap code (BBC). On both synthetic data and real application data, the new word-aligned schemes use only 50% more space, but perform logical operations on compressed data 12 times faster than BBC. The new schemes achieve this performance advantage by guaranteeing that during logical operations every machine instruction performs useful work on words rather than on bytes or bits as in BBC.

full text of LBNL-48975 (PDF)

Final version appeared in CIKM 2001. This is based on an extensive evaluation of many different bitmap compression methods, including PackBits, Byte-aligned Bitmap Code (BBC), Word-aligned Bitmap Code (WBC), Word-Aligned Hybrid (WAH), Gzip and Bzip2.
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