, 2006). The queries are evaluated
with bitwise logical operations that are well supported by computer hardware. For
an attribute with c distinct values, the basic bitmap index generates c bitmaps with
N bits each, where N is the number of records (rows) in the dataset. Each bit in a
bitmap is set to ???1??? if the attribute in the record is of a specific value; otherwise
the bit is set to ???0???. Figure 1 shows a simple bitmap index with six bitmaps. Each
bitmap represents a distinct attribute value. For instance, the attribute value 3 is
highlighted to demonstrate the encoding. In this case, bitmap 3 is set to ???1???, all
other bits on the same horizontal position are set to ???0???.
Encoding
The basic bitmap index introduced is also called equality-encoded bitmap index
since each bitmap indicates whether or not an attribute value equals to the key.
This strategy is the most efficient for equality queries such as ???temperature = 100.???
Chan and Ioannidis (1998, 1999) developed two other encoding strategies that are
called range encoding and interval encoding. These bitmap indices are optimized
for one-sided and two-sided range queries, respectively. An example of a one-sided
range query is ???pressure < 56.7???. A two-sided range query, for instance, is ???35.8 <
pressure < 56.7???.
Figure 1. Simple bitmap index with six bitmaps to represent six distinct attribute
values
62 Stockinger & Wu
Copyright ?© 2007, Idea Group Inc.
Pages:
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320