Range-based bitmap indexing
Bucket
Number
Ranges
on Age
Number of
Persons Tuple [1, 16) [16, 28) [28, 40) [40, 60) [60, 65)
1 [1, 16) 21 1 1 0 0 0 0
2 [16, 28) 22 2 0 0 0 1 0
3 [28, 40) 21 3 0 0 1 0 0
4 [40, 60) 22 4 0 1 0 0 0
5 [60, 65) 23 5 0 0 0 0 1
(a) Population of Each Bucket (b) Bitmap Representation of Example Tuples
Indexing in Data Warehouses 8
Copyright ?© 2007, Idea Group Inc. Copying or distributing in print or electronic forms without written permission
of Idea Group Inc. is prohibited.
bucket ranges by counting the data points falling into each bucket. If the bucket
grows beyond a threshold, it is expanded into smaller-range buckets. Adjacent buckets
are then combined into the final required number of buckets that are approximately
balanced. The bitmap vectors are built with another scan of the data.
Table 3(a) shows five nearly-equally populated bucket ranges on the attribute Age,
constructed by the RBBI technique. The range-based bitmap index for the first 5
tuples of a database with 109 tuples is shown in Table 3(b). Note that the records
are nearly evenly distributed in the 5 buckets.
The ranges are continuous-valued intervals and mutually exclusive. Thus, RBBI can
effectively answer range and point queries, though it results in retrieval of excess
tuples since all the tuples within the queried range are retrieved and the excess has
to be filtered out.
Pages:
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360