The bitmap index, on the
other hand, has excellent performance characteristics on these queries. As shown
with both theoretical analyses and timing measurements, a compressed bitmap
index can be very efficient in answering one-dimensional range queries (Stockinger,
Wu, & Shoshani, 2002; Wu, Otoo, & Shoshani, 2004, 2006). Since answers
to one-dimensional range queries can be efficiently combined to answer arbitrary
60 Stockinger & Wu
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
multidimensional range queries, compressed bitmap indices are efficient for any
range query. In terms of computational complexity, one type of compressed bitmap
index was shown to be theoretically optimal for one-dimensional range queries. The
reason for the theoretically proven optimality is that the query response time is a
linear function of the number of hits, that is, the size of the result set. There are a
number of indexing methods, including B*-tree and B+-tree (Comer, 1979), that are
theoretically optimal for one-dimensional range queries, but most of them cannot
be used to efficiently answer arbitrary multidimensional range queries.
The bitmap index in its various forms was used a long time before relational database
systems or data warehousing systems were developed.
Pages:
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317