If they
are encoded separately as in an SBI, it results in five bitmaps. By encoding more
than one value in a bitmap, the number of vectors is reduced to two. Attribute values
{1, 2} and {3, 4, 5} are jointly encoded. A query referencing attribute value 2
retrieves tuples having the attribute value 1 along with the ones having the value 2.
Therefore, it is vital to minimize the number of false hits that each bitmap returns,
since these tuples have to be retrieved and filtered out in a post-processing phase.
The essential idea is the same as the SBI in that a bit (1 or 0) is used to indicate
Table 2. Koudas??™ encoded bitmap index
A {1,2}
{3,4,5}
2 0 1
4 0 1
1 1 0
5 0 1
3 1 0
84 Davis & Gupta
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
whether an attribute in a tuple is equal to a specific value (here, a set of values) or
not. The choice of attribute values to jointly encode depends on the frequency of
access of each attribute value as well as the frequency of occurrence of the value in
the attribute instances. The mutually exclusive range of consecutive attribute values
encoded together in the same bitmap is called the range of that bitmap.
The author compares KEBI with a strategy in which the attribute values are divided
into approximately equal length ranges.
Pages:
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358