Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
a one-to-one mapping and a set of retrieval Boolean functions. Table 4 shows an
EBI for an attribute A with domain {a, b, c, d}. NULL and non-existing values are
encoded with the domain, so that the total number of domain values is 6 (NotExist,
NULL, a, b, c, and d.) The number of bit-vectors required is ??®log2 6??? = 3.
To retrieve data, a Boolean function is defined for each value. If a value v with a
domain of size k is encoded as b1b0 (bi ??? {0, 1}, i = 0 to ??®log2 k??? -1), then the retrieval
function for v is defined as x1x0, where xi = Bi if bi =1, otherwise xi is equal to the
negation of Bi, i.e., xi = Bi??™. The number of bitmap vectors accessed is minimized
as a result of a well-defined encoding.
Compared to SBI, the EBI improves space utilization and solves sparsity problems.
It performs efficiently with wide-range queries. In an environment where selection
patterns can be pre-defined, the main idea of EBI is to establish a well-defined encoding
so that time efficiency can be improved without sacrificing space efficiency.
Encoding schemes are crucial since Boolean operations can be performed on the
retrieval functions before retrieving the data, reducing the total number of operations
performed and bitmap vectors accessed.
Pages:
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362