Bitmap indexes are useful in processing complex, read-only
queries in decision support systems, and have been implemented
in several commercial database systems.
A key design parameter for bitmap index is its encoding scheme which
determines the set of attribute values represented by each bitmap in an
index.
While the relative performance of the two existing bitmap encoding schemes
for simple selection queries of the form "v1 <= A <= v2 " is known
(specifically, one of the encoding schemes is better for processing
equality queries; i.e., v1 = v2,
while the other is better for processing range queries; i.e., v1 < v2),
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 established a number of optimality results
for the existing encoding schemes for a number of query classes;
in particular, we proved that neither of the two known schemes
is optimal for the class of two-sided range queries.
We also proposed a new encoding scheme and proved that it is an optimal
encoding scheme for the class of two-sided range queries.
We also conducted an experimental study comparing the performance of
the new encoding scheme with the existing as well as four hybrid encoding
schemes
for both simple selection queries and the more general class
of membership queries of the form "A in { v1, v2, ...., vn }".
Our results show that the new encoding scheme has overall
better space-time tradeoff than existing schemes.