Defining a good encoding scheme is
a difficult and open problem. In addition, EBI performance degrades for equality
queries since all the bitmap vectors have to be searched. Due to these drawbacks, we
do not consider EBI for further comparison here. Variations of the EBI for specific
scenarios are given by Wu and Buchmann (1998) and listed in our classification in
Figure 1 under EBI techniques.
Bit-Sliced.Index
A bit-sliced index (BSI) (O??™Neil & Quass, 1997; Chan & Ioannidis, 1998) is a set
of bitwise projections of an attribute. BSIs are total-order preserving, hence they
are suitable for representing numeric (fixed-point) or ordinal types of attributes,
and are especially good for wide-range searches. The design space of a BSI is de-
fined by two factors, attribute value decomposition and encoding scheme (Chan &
Ioannidis, 1998).
The first factor, attribute value decomposition (AVD), defines the arithmetic to
represent the values of an attribute. It is the decomposition of an attribute??™s values
in digits according to a chosen base. For example, 124 can be decomposed into
<1, 2, 4> according to base <10, 10, 10>. The second factor that defines a BSI is
the encoding scheme. Consider the ith component of an index with a base value bi.
There are two schemes to directly encode the corresponding values vi (0 <= vi <=
bi ??“1) in bits, equality encoding and range encoding.
Pages:
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363