Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes
| dc.creator | Kaser, Owen | |
| dc.creator | Lemire, Daniel | |
| dc.creator | Aouiche, Kamel | |
| dc.date | 2008-08-15 | |
| dc.date | 2009-01-19 | |
| dc.date.accessioned | 2026-07-07T12:30:54Z | |
| dc.date.available | 2026-07-07T12:30:54Z | |
| dc.description | 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%. | |
| dc.description | To appear in proceedings of DOLAP 2008 | |
| dc.identifier | https://arxiv.org/abs/0808.2083 | |
| dc.identifier | http://arxiv.org/abs/0808.2083 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/216277 | |
| dc.subject | Databases | |
| dc.subject | H.3.2; E.1 | |
| dc.title | Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes | |
| dc.type | text |