One can use a
simple bitmap encoding method to encode the values of c1 and c2 separately. Next,
we give a more specific example to illustrate the multicomponent encoding.
Figure 3 illustrates a 2-component encoded bitmap index for an attribute with cardinality
c = 1000. In our example, the two components have base sizes of b1 = 25
and b2 = 40. Assume the attribute values are in the domain of [0; 999]. An attribute
value v is decomposed into two components with c1 = v / 40 and c2 = v % 40.
The component c1 can be treated as an integer attribute in the range of 0 and 24;
the component c2 can be viewed as an integer attribute in the range of 0 and 39.
Two bitmap indices can be built, one for each component, for example, c1 with the
equality encoding and c2 with range encoding. If range encoding is used for both
components, it uses 24 bitmaps for Component 1, and 39 bitmaps for Component
2. In this case, the 2-component encoding uses 63 bitmaps, which is more than the
10 bitmaps used by binary encoding. To answer the same query ???v < 105??? using
the 2-component index, the query is effectively translated to ???c1<2 OR (c1=2 AND
Component 1
b1 = 25
c1<=0
c1<=1
c1<=2
??¦
c1<=23
Component 2
b2 = 40
c2<=0
c2<=1
c2<=2
??¦
c2<=38
Figure 3. An illustration of a 2-component bitmap index
64 Stockinger & Wu
Copyright ?© 2007, Idea Group Inc.
Pages:
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324