This encoding method uses only rather than c/2 bitmaps, where c is the attribute
cardinality. For an integer attribute in the range of 0 and c-1, each bitmap in the
bitmap index is a concatenation of one of the binary digits for every record. For
an attribute with c=1000, it only needs 10 bitmaps. The advantage of this encoding
is that it requires much fewer bitmaps than interval encoding. However, to answer
a range query, using interval encoding one has to access only two bitmaps whereas
using binary encoding one usually has to access all bitmaps.
A number of authors have proposed strategies to find the balance between the space
and time requirements (Chan & Ioannidis, 1999; Wong et al., 1985). A method
proposed by Chan and Ioannidis (1999) called multicomponent encoding can be
thought of as a generalization of binary encoding. In the binary encoding, each
bitmap represents a binary digit of the attribute values; the multicomponent encoding
breaks the values in a more general way, where each component could have a
different size. Consider an integer attribute with values ranging from 0 to c-1. Let
b1 and b2 be the sizes of two components c1 and c2, where b1*b2>=c. Any value
v can be expressed as v = c1*b2+c2, where c1 = v / b2 and c2 = v % b2, where ???/??™
denotes the integer division and ???%??™ denotes the modulus operation.
Pages:
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323