  Compressed bitmap indexes are used to speed up simple aggregate queries in
databases. Indeed, set operations like intersections, unions and complements
can be represented as logical operations (AND,OR,NOT) that are ideally suited
for bitmaps. However, it is less obvious how to apply bitmaps to more advanced
queries. For example, we might seek products in a store that meet some, but
maybe not all, criteria. Such threshold queries generalize intersections and
unions; they are often used in information-retrieval and data-mining
applications. We introduce new algorithms that are sometimes three orders of
magnitude faster than a naive approach. Our work shows that bitmap indexes are
more broadly applicable than is commonly believed.
