Database Reference
In-Depth Information
(a) Input bitmap with 5456 bits
10000000000000000000011100000000000000000000000.....................0000000000000001111111111111111111111111
(b) Group bits into 176 31-
bit groups
31 bits
31 bits
31 bits
(c) Merge neighboring groups with identical bits
31 bits
174*31 bits
31 bits
(d) Encode each group using one
word
100...010101110
001...11
01000
Run length is 174
31 literal bits
31 literal bits
Fill bit 0
Bit 0 indicates “tail” word
Bit 1 indicates “fill” word
Bit 0 indicates “tail” word
Run 1
Run 2
(a) An illustration of WAH
10
1
10
0
10
-1
DBMS B-tree
DBMS bitmap index
FastBit index
10
-2
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
Fraction of Hits
(b) Time (s) to answer queries
Figure 6.16
The effects of compression on query response time. The faster
WAH compression used in FastBit reduces the query response time by an order
of magnitude. (Illustration adapted from Stockinger, 16, and 2006.
Bitmap
indicies for data warehouses
. Idea Group, Inc. used with permission from
TGI Global.
89
)
