Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
c2<25).??? Evaluating this expression requires three bitmaps representing ???c1<=1,???
???c1<=2,??? and ???c2<=24.??? In contrast, using the binary encoded bitmap index to
evaluate the same query, all 10 bitmaps are needed.
Using more components can reduce the number of bitmaps and therefore reduces
the total index size. However, using more components will also increase the number
of bitmaps accessed in order to answer a query, hence increasing the query response
time. Clearly, there is a trade-off between the index size and the query response
time. Without considering compression, Chan and Ioannidis (1999) have analyzed
this space-time trade-off. They suggested that the inflection point of the trade-off
curve is at two components. They further suggested that the two components should
have nearly the same base sizes to reduce the index size.
Binning
The simplest form of bitmap indices works well 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 ???distinct temperature
values in a supernova explosion,??? simple bitmap indices are impractical due to
large storage and computational complexities.
Pages:
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325