Each
attribute is encoded in such a way that the number of bitmap vectors retrieved to
answer a query is reduced compared to the SBI. Bit-sliced index techniques are
shown in Figure 1(c). They are based on the idea of attribute value decomposition,
that is, decomposition of an attribute value in digits according to some base, either
uniform or non-uniform. They can be either range or equality encoded.
BIs comparable to the novel technique introduced in the third section are discussed
in further detail below. We select one technique for comparison in the fourth section
based on three criteria: suitability for processing range queries, published design
algorithms for the index, and research results indicating that the technique is competitive
with other known techniques. Note that bitmap compression techniques
are not considered here; they are discussed in the future work section.
Simple.Bitmap.Index
The basic idea of a simple bitmap index (also called Pure BI) (O??™Neil & Quass,
1997) is to use a bit (0 or 1) to indicate whether an attribute in a tuple is equal to
a specific value or not. The sparsity of the bit-vectors increases with increasing
cardinality of the indexed attribute and number of tuples in the database, resulting
in poor space utilization and high processing cost. Hence, as the cardinality of the
indexed attribute and the database size increases, both time and space complexity
of building and maintaining an SBI rapidly becomes higher (Wu & Buchmann,
1998).
Pages:
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355