Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes [r-libre/223]

Kaser, Owen, Lemire, Daniel ORCID: https://orcid.org/0000-0003-3306-6922 et Aouiche, Kamel (2008). Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes. Dans Proceedings of the 11th ACM International Workshop on Data Warehousing and OLAP (p. 1-8). ACM. 10.1145/1458432.1458434

Fichier(s) associé(s) à ce document :

PDF - 0808.2083v3.pdf

Télécharger

Catégorie de document :	Communications dans des actes de congrès/colloques
Évaluation par un comité de lecture :	Oui
Étape de publication :	Publié
Résumé :	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%.
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	22 juill. 2014 21:48
Dernière modification :	05 nov. 2026 20:33

Actions (connexion requise)

RÉVISER