Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
A comparison of an equality-encoded and range-encoded bitmap index is given in
Figure 2 (based on Chan & Ioannidis, 1999). Let us look at the encoding of value
2, which is highlighted in the figure. For equality encoding, the third bitmap is set
to ???1??? (E2), whereas all other bits on the same horizontal line are set to ???0???. For the
range-encoded bitmap index, all bits between bitmap R2 and R8 are set to ???1???, the
remaining bits are set to ???0???. This encoding is very efficient for evaluating range
queries. Consider, for instance, the query ???A <= 4???. In this case, at most one bitmap,
namely bitmap R4, has to be accessed (scanned) for processing the query. All bits
that are set to ???1??? in this bitmap fulfill the query constraint. On the other hand, for
the equality-encoded bitmap index, the bitmaps E0 to E4 have to be ORed together
(via the Boolean operator OR). This means that 5 bitmaps have to be accessed, as
opposed to only 1 bitmap for the case of range encoding. In short, range encoding
requires at most one bitmap scan for evaluating range queries, whereas equality
encoding requires in the worst case c/2 bitmap scans, where c corresponds to the
number of bitmaps. Since one bitmap in range encoding contains only ???1???s, this
bitmap is usually not stored.
Pages:
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321