Scatter Bitmap: Space-Time Efficient Bitmap Indexing for Equality and Membership Queries

Abstract

In a data warehouse environment, indexing techniques based on bitmap representations are useful for answering complex and ad hoc queries efficiently without adding additional hardware. They significantly improve query processing time by utilizing low-cost Boolean operations and multiple indices scans, executing queries by performing simple predicate conditions on the index level before going to the primary data source. In this paper, we propose a new bitmap called scatter bitmap index that uses less space than existing bitmap indices while maintaining query processing time. Our scatter bitmap index achieves this by representing each attribute value using only two bitmap vectors, but each bitmap vector represents many attribute values. Our experimental results confirm that the performance of our scatter bitmap index is better than those found by existing techniques for equality and membership queries from the point of view of space-time tradeoff