However,
operations on BBC compressed bitmaps are usually faster (Johnson, 1999). Clearly,
there is a worthwhile space-time trade-off. The WAH compression takes this spacetime
trade-off one step further. More specifically, WAH compressed bitmaps are
larger than BBC compressed ones, but operations on WAH compressed bitmaps are
much faster than on BBC compressed ones. Therefore, WAH compressed bitmap
indices can answer queries much faster as demonstrated in a number of different
experiments (Stockinger et al., 2002; Wu et al., 2006). In the next section we provide
a detailed description of the WAH compression. For more information on BBC, we
refer the reader to Antoshenkov (1994) and Antoshenkov & Ziauddin (1996).
WAH.Bitmap.Compression
The WAH bitmap compression is based on run-length encoding, where consecutive
identical bits are represented with their bit value (0 or 1) and a count (length of the
run). In WAH each such run consists of a fill and a tail. A fill is a set of consecutive
identical bits that is represented as a count plus their bit value. A tail is a set of
mixed 0s and 1s that is represented literally without compression. One key idea of
Bitmap Indices for Data Warehouses 6
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
Pages:
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330