While RBBI is designed for range queries, it is not chosen for the
performance study discussed in this chapter; we choose a BSI technique because its
developers give compelling results regarding its competitive performance.
Encoded.Bitmap.Index
The encoded bitmap index (EBI) (Wu & Buchmann, 1998) has been proposed to
index large cardinality domains since they are not efficiently indexed by SBI. The
basic idea is to encode each value of the attribute domain as a binary number, rather
than have a bit-vector for each value as in an SBI. Each distinct value of an attribute
is encoded using a number of bits, each of which is stored in a bitmap vector. For
example, if attribute A has 12,000 different values, then an SBI has 12,000 bitmap
vectors. Encoded bitmap indexing uses only ??®log2 12000???, i.e., 14 bitmap vectors
and a mapping table. A lookup table stores the mapping between A and its encoded
representation. Cases for NULL values or non-existing tuples are encoded together
with other domain values so separate existence vectors are not required, as in the
case of SBIs. An EBI on a column A of table T consists of a set of bitmap vectors,
Table 4. Encoded bitmap indexing
A B2 B1 B0 NULL 000 fa B2??™B1B0??™
b 0 1 1 NotExist 001 fb B2??™B1B0
a 0 1 0 a 010 fc B2B1??™B0??™
d 1 0 1 b 011 fd B2B1??™B0
c 1 0 0 c 100
NULL 0 0 0 d 101
(a) Bitmap vector (b) Mapping table for A (c) Retrieval functions
86 Davis & Gupta
Copyright ?© 2007, Idea Group Inc.
Pages:
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361