Journal article
Hybrid query optimization for hard-to-compress bit-vectors
The VLDB journal, Vol.25(3), pp.339-354
06/2016
DOI: 10.1007/s00778-015-0419-9
Abstract
Bit-vectors are widely used for indexing and summarizing data due to their efficient processing in modern computers. Sparse bit-vectors can be further compressed to reduce their space requirement. Special compression schemes based on run-length encoders have been designed to avoid explicit decompression and minimize the decoding overhead during query execution. Moreover, highly compressed bit-vectors can exhibit a faster query time than the non-compressed ones. However, for hard-to-compress bit-vectors, compression does not speed up queries and can add considerable overhead. In these cases, bit-vectors are often stored verbatim (non-compressed). On the other hand, queries are answered by executing a cascade of bit-wise operations involving indexed bit-vectors and intermediate results. Often, even when the original bit-vectors are hard to compress, the intermediate results become sparse. It could be feasible to improve query performance by compressing these bit-vectors as the query is executed. In this scenario, it would be necessary to operate verbatim and compressed bit-vectors together. In this paper, we propose a hybrid framework where compressed and verbatim bitmaps can coexist and design algorithms to execute queries under this hybrid model. Our query optimizer is able to decide at run time when to compress or decompress a bit-vector. Our heuristics show that the applications using higher-density bitmaps can benefit from using this hybrid model, improving both their query time and memory utilization.
Details
- Title: Subtitle
- Hybrid query optimization for hard-to-compress bit-vectors
- Creators
- Gheorghi Guzun - 4016 Seamans Center for the Engineering Arts and Sciences The University of Iowa Iowa City IA USAGuadalupe Canahuate - 4016 Seamans Center for the Engineering Arts and Sciences The University of Iowa Iowa City IA USA
- Resource Type
- Journal article
- Publication Details
- The VLDB journal, Vol.25(3), pp.339-354
- Publisher
- Springer Berlin Heidelberg
- DOI
- 10.1007/s00778-015-0419-9
- ISSN
- 1066-8888
- eISSN
- 0949-877X
- Language
- English
- Date published
- 06/2016
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083893302771
Metrics
13 Record Views