Myriad data-management applications use bitmap indices to improve query-processing performance. In a bitmap index a relation's attributes are discretized into bins representing discrete ranges of values. A wide array of query types can be constructed through the application of boolean operators across sets of bins. However, for certain applications in which attribute values tend to be continuous and precise, bitmap indices must be generated with high dimensionality, i.e., a large number of bins per attribute. In such cases, bitmap-processing performance tends to deteriorate.

In this paper, we present a caching framework that accelerates range and point queries over high-cardinality bitmap indices. The framework organizes, manages, and seamlessly integrates partial or intermediate results for query processing. We show that for general-case disjunctive and conjunctive queries, selecting the optimal set of partial results required to resolve the query is NP-complete. However, for common consecutive range queries and point queries, we provide a provably-optimal greedy selection algorithm. We extensively evaluate of our system over the TPC-H benchmark, and we also present a case study involving real network-intrusion data. Our study results show that our framework can achieve over 140-time speedup on highly variable query workloads.