Range-based bitmap indexing for high cardinality attributes with skew

Abstract

Bitmap indexing, though effective for low cardinality attributes, can be rather costly in storage overhead for high cardinality attributes. Range-based bitmap (RBM) indexing can be used to reduce this storage overhead. The attribute values are partitioned into ranges and a bitmap vector is used to represent a range. With RBM, however, the number of records assigned to different ranges can be highly uneven, resulting in non-uniform search times for different queries. We present and evaluate a dynamic bucket expansion and contraction (DBEC) approach to simultaneously constructing range-based bitmap indexes for multiple high-cardinality attributes. Simulations are conducted to evaluate this DBEC approach. Both synthetic and real data are used in the simulations. The results show that (1) with highly skewed data, DBEC performs quite well compared with a simple approach and (2) DBEC compares favorably with the optimal approach.