An efficient bitmap encoding scheme for selection queries

Bitmap indexes are useful in processing complex queries in decision support systems, and they have been implemented in several commercial database systems. A key design parameter for bitmap indexes is the encoding scheme, which determines the bits that are set to 1 in each bitmap in an index. While the relative performance of the two existing bitmap encoding schemes for simple selection queries of the form “v₁ ≤ A ≤ v₂” is known (specifically, one of the encoding schemes is better for processing equality queries; i.e., v₁ = v₂, while the other is better for processing range queries; i.e., v₁ < v₂), it remains an open question whether these two encoding schemes are indeed optimal for their respective query classes in the sense that there is no other encoding scheme with better space-time tradeoff. In this paper, we establish a number of optimality results for the existing encoding schemes; in particular, we prove that neither of the two known schemes is optimal for the class of two-sided range queries. We also propose a new encoding scheme and prove that it is optimal for that class. Finally, we present an experimental study comparing the performance of the new encoding scheme with that of the existing ones as well as four hybrid encoding schemes for both simple selection queries and the more general class of membership queries of the form “A ∈ {v₁, v₂, .…, v_k}”. These results demonstrate that the new encoding scheme has an overall better space-time performance than existing schemes.