, 2002;
Wu et al., 2002).
The basic bitmap index uses each distinct value of the indexed attribute as a key,
and generates one bitmap containing as many bits as the number of records in the
dataset for each key (O??™Neil, 1987). Let the attribute cardinality be the number of
distinct values present in a dataset. The size of a basic bitmap index is relatively small
for low-cardinality attributes, such as ???gender,??? ???types of cars sold per month,??? or
???airplane models produced by Airbus and Boeing.??? However, for high-cardinality
attributes such as ???temperature values in a supernova explosion,??? the index sizes
may be too large to be of any practical use. In the literature, there are three basic
strategies to reduce the sizes of bitmap indices: (1) using more complex bitmap
encoding methods to reduce the number of bitmaps or improve query efficiency,
(2) compressing each individual bitmap, and (3) using binning or other mapping
strategies to reduce the number of keys. In the remaining discussions, we refer to
these three strategies as encoding, compression, and binning, for short.
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.
Bitmap. Index. Design
Basic.Bitmap.Index
Bitmap indices are one of the most efficient indexing methods available for speeding
up multidimensional range queries for read-only or read-mostly data (O??™Neil,
1987; Rotem, Stockinger & Wu, 2005b; Wu et al.
Pages:
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319