Table 5. A range-encoded decimal (base-10) bit-sliced index
A B B B B B0 B B B B B B0 B ??¦ B B B B B B0
124 1 1 ??¦ 1 1 0 1 1 ??¦ 1 1 0 0 1 ??¦ 1 1 0 0 0 0
??¦
Component 3 Component 2 Component 1
88 Davis & Gupta
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission of
Idea Group Inc. is prohibited.
Beyond. Bitmaps:.The.Property.Map
There are two characteristics of bitmap indexes that we modify in order to consider
a new kind of bitmap. One is that bitmap indexes generally create encodings based
on values only; we propose encodings based on values and driven by application
knowledge, e.g., queries. In this respect, our technique is similar to EBI (Wu & Buchmann,
1998), however, how to design the encoding of an EBI is an open question.
The second is that bitmap indexes are generally single attribute-only; we propose a
solution that supports multi-attribute queries directly. RBBI (Wu & Yu, 1998) has
a similar notion of range-encoding, but our technique supports additional encoding
schemes. The novel technique introduced here is called a Property Map. The basic
concept is defined and illustrated below and then its performance is compared to
the REBSI technique in the following section.
A property map (PMap) defines properties on each attribute depending on knowledge
of the application, such as a known set of queries.
Pages:
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366