In equality encoding, the bit
in a component is set if equality condition is satisfied and there are bi bits, one for
each possible value. The representation of value vi has all bits set to 0, except for
Indexing in Data Warehouses 8
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
the bit corresponding to vi, which is set to 1. Thus, an equality encoded bit-sliced
index (EEBSI) component with base bi consists of bi bitmaps.
In range-encoding, there are bi bits (one for each possible value) set so as to satisfy
an inequality condition between the value represented by them and the decomposed
attribute value of the corresponding record for that component. The representation
of value vi has the vi rightmost (or leftmost) bits set to 0 and the remaining bits
(starting from the one corresponding to vi, and to the left (or right)) are set to 1. In
the example shown in Table 5, the bitmaps are less than or equal to encoded. For
the attribute value 124, 1 is represented by component 3, 2 by component 2 and 4
by component 1. The representation of 1 has one rightmost bit set to 0 and the rest
set to 1, the representation of 2 has two rightmost bits set to 0 and the rest set to 1,
and so on. Intuitively, each bitmap Bivi has 1 in all the records whose ith component
value is less than or equal to vi.
Pages:
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364