Therefore, there are only c-1 bitmaps in a range-encoded
index.
Assuming each attribute value fits in a 32-bit machine word, the basic bitmap index
for an attribute with cardinality 32 takes as much space as the base data (known
as user data or original data). Since a B-tree index for a 32-bit attribute is often
observed to use three or four times the space as the base data, many users consider
only attributes with cardinalities less than 100 to be suitable for using bitmap indices.
Clearly, controlling the size of the bitmap indices is crucial to make bitmap
indices practically useful for higher cardinality attributes. The interval-encoding
scheme (Chan & Ioannidis, 1999) reduces the number of bitmaps only by a factor
2. Thus, other techniques are needed to make bitmap indices practical for high
cardinality attributes.
Figure 2. Equality-encoded bitmap index (b) compared with range-encoded bitmap
index (c). The leftmost column shows the row ids (RID) for the data values represented
by the projection index shown in (a).
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.
The encoding method that produces the least number of bitmaps is binary encoding
introduced by Wong et al. (1985). Binary encoding was later used by various authors
(O??™Neil & Quass, 1997; Wu & Buchmann, 1998) in the context of bitmap indices.
Pages:
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322