Conference proceeding
A tunable compression framework for bitmap indices
2014 IEEE 30th International Conference on Data Engineering, pp.484-495
03/2014
DOI: 10.1109/ICDE.2014.6816675
Abstract
Bitmap indices are widely used for large read-only repositories in data warehouses and scientific databases. Their binary representation allows for the use of bitwise operations and specialized run-length compression techniques. Due to a trade-off between compression and query efficiency, bitmap compression schemes are aligned using a fixed encoding length size (typically the word length) to avoid explicit decompression during query time. In general, smaller encoding lengths provide better compression, but require more decoding during query execution. However, when the difference in size is considerable, it is possible for smaller encodings to also provide better execution time. We posit that a tailored encoding length for each bit vector will provide better performance than a one-size-fits-all approach. We present a framework that optimizes compression and query efficiency by allowing bitmaps to be compressed using variable encoding lengths while still maintaining alignment to avoid explicit decompression. Efficient algorithms are introduced to process queries over bitmaps compressed using different encoding lengths. An input parameter controls the aggressiveness of the compression providing the user with the ability to tune the tradeoff between space and query time. Our empirical study shows this approach achieves significant improvements in terms of both query time and compression ratio for synthetic and real data sets. Compared to 32-bit WAH, VAL-WAH produces up to 1.8× smaller bitmaps and achieves query times that are 30% faster.
Details
- Title: Subtitle
- A tunable compression framework for bitmap indices
- Creators
- Gheorghi Guzun - University of IowaGuadalupe Canahuate - University of IowaDavid Chiu - Washington State University VancouverJason Sawin - University of St. Thomas (Minnesota)
- Resource Type
- Conference proceeding
- Publication Details
- 2014 IEEE 30th International Conference on Data Engineering, pp.484-495
- Publisher
- IEEE
- DOI
- 10.1109/ICDE.2014.6816675
- ISSN
- 1063-6382
- eISSN
- 2375-026X
- Language
- English
- Date published
- 03/2014
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197302202771
Metrics
9 Record Views