Journal article
Performance evaluation of word-aligned compression methods for bitmap indices
Knowledge and information systems, Vol.48(2), pp.277-304
08/2016
DOI: 10.1007/s10115-015-0877-9
Abstract
Bitmap indices are a widely used scheme for large read-only repositories in data warehouses and scientific databases. This binary representation allows the use of bit-wise operations for fast query processing and is typically compressed using run-length encoding techniques. Most bitmap compression techniques are aligned using a fixed encoding length (32 or 64 bits) to avoid explicit decompression during query time. They have been proposed to extend or enhance word-aligned hybrid (WAH) compression. This paper presents a comparative study of four bitmap compression techniques: WAH, PLWAH, CONCISE, and EWAH. Experiments are targeted to identify the conditions under which each method should be applied and quantify the overhead incurred during query processing. Performance in terms of compression ratio and query time is evaluated over synthetic-generated bitmap indices, and results are validated over bitmap indices generated from real data sets. Different query optimizations are explored, query time estimation formulas are defined, and the conditions under which one method should be preferred over another are formalized.
Details
- Title: Subtitle
- Performance evaluation of word-aligned compression methods for bitmap indices
- Creators
- Gheorghi Guzun - Department of Electrical and Computer Engineering The University of Iowa Iowa City IA USAGuadalupe Canahuate - Department of Electrical and Computer Engineering The University of Iowa Iowa City IA USA
- Resource Type
- Journal article
- Publication Details
- Knowledge and information systems, Vol.48(2), pp.277-304
- Publisher
- Springer London
- DOI
- 10.1007/s10115-015-0877-9
- ISSN
- 0219-1377
- eISSN
- 0219-3116
- Language
- English
- Date published
- 08/2016
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083824802771
Metrics
19 Record Views