Open access research
publication repository
publication repository
Kaser, Owen; Lemire, Daniel, & Aouiche, Kamel (2008). Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes. In Proceedings of the 11th ACM International Workshop on Data Warehousing and OLAP. ACM.
File(s) available for this item:| PDF - 0808.2083v3.pdf |
|
| Item Type: | Papers in Conference Proceedings |
|---|---|
| Refereed: | Yes |
| Status: | Published |
| Abstract: | Bitmap indexes must be compressed to reduce input/output costs and minimize CPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we use techniques based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. These techniques are sensitive to the order of the rows: a simple lexicographical sort can divide the index size by 9 and make indexes several times faster. We investigate reordering heuristics based on computed attribute-value histograms. Simply permuting the columns of the table based on these histograms can increase the sorting efficiency by 40%. |
| Depositor: | Lemire, Daniel |
| Owner / Manager: | Daniel Lemire |
| Deposited: | 22 Jul 2014 21:48 |
| Last Modified: | 16 Jul 2015 00:47 |
|
RÉVISER |
