In this chapter we discuss an indexing technology that holds a great promise in
breaking the curse of dimensionality for data warehousing applications, namely
the bitmap index. A very noticeable character of a bitmap index is that its primary
solution to a query is a bitmap. One way to break the curse of dimensionality is to
build a bitmap index for each attribute of the dataset. To resolve a query involving
conditions on multiple attributes, we first resolve the conditions on each attribute
using the corresponding bitmap index, and obtain a solution for each condition as a
bitmap. We then obtain the answer to the overall query by combining these bitmaps.
Because the operations on bitmaps are well supported by computer hardware, the
bitmaps can be combined easily and efficiently. Overall, we expect the total query
response time to scale linearly in the number of attributes involved in the query,
rather than exponentially in the number of dimensions (attributes) of the dataset,
thus breaking the curse of dimensionality.
These statements omitted many technical details that we will elaborate in this chapter.
In the next section we give a broad overview of the bitmap index and its relative
strengths and weaknesses to other common indexing methods. We then describe the
basic bitmap index and define the terms used in the discussions. We devote a large
portion of this chapter to review the three orthogonal sets of strategies to improve
the basic bitmap index.
Pages:
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314