Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
Chapter.VII
Bitmap.Indices.for.
Data.Warehouses
Kurt Stockinger
Lawrence Berkeley National Laboratory, University of California, USA
Kesheng Wu
Lawrence Berkeley National Laboratory, University of California, USA
Abstract
In this chapter we discuss various bitmap index technologies for efficient query
processing in data warehousing applications. We review the existing literature and
organize the technology into three categories, namely bitmap encoding, compression,
and binning. We introduce an efficient bitmap compression algorithm and
examine the space and time complexity of the compressed bitmap index on large
datasets from real applications. According to the conventional wisdom, bitmap
indices are only efficient for low-cardinality attributes. However, we show that the
compressed bitmap indices are also efficient for high-cardinality attributes. Timing
results demonstrate that the bitmap indices significantly outperform the projection
index, which is often considered to be the most efficient access method for multidimensional
queries. Finally, we review the bitmap index technology currently supported
by commonly used commercial database systems and discuss open issues
for future research and development.
158 Stockinger & Wu
Copyright ?© 2007, Idea Group Inc.
Pages:
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312