We conclude with guidelines for improving query
processing performance for complex range queries.
Background
Bitmap indexes are designed for different query types including range, aggregation
and join queries. Figure 1 shows tree diagrams of bitmap indexes, which we classify
into three categories based on their main features. Figure 1(a) shows bitmap
indexing methods that use the simple bitmap index (SBI) representation described
in the previous section. The techniques that use clustering of attribute values are
Figure 1. Classification of bitmap indexing techniques
Range-based BI
(RBBI)
Simple BI (SBI)
Applications
Dynamic BI
(DBI)
Clustering
Koudas BI
(KEBI)
Bitmap Join Index
(BJI) (a)
Bit-Sliced Index (BSI)
(Uniform or Non-Uniform Base)
Equality Encoded
(EEBSI)
Range Encoded
(REBSI)
(c)
Encoded BI (EBI)
Total-Order Preserving
Encoding (TOPE)
Range-based
Encoding (RE)
(b)
Hierarchy Encoding
(HE)
Groupset (GI)
82 Davis & Gupta
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
grouped in one category. The other category consists of techniques that are basically
applications of SBI. Figure 1(b) shows encoded bitmap index (EBI) techniques
that use binary encoding along with a mapping table and retrieval functions.
Pages:
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354