⚠️ Maintenance r-Libre

Des travaux de maintenance entraîneront une indisponibilité de la plateforme le lundi 04 mai 2026 (toute la journée).
Merci de votre compréhension.

LogoTeluq

Répertoire de publications
de recherche en accès libre

Sorting improves word-aligned bitmap indexes [r-libre/228]

Lemire, Daniel, Kaser, Owen et Aouiche, Kamel (2010). Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering, 69 (1), 3-28. 10.1016/j.datak.2009.08.006

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

[thumbnail of 0901.3751v5.pdf]

PDF - 0901.3751v5.pdf

Catégorie de document :	Articles de revues
É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 row-reordering heuristics. Simply permuting the columns of the table can increase the sorting efficiency by 40%. Secondary contributions include efficient algorithms to construct and aggregate bitmaps. The effect of word length is also reviewed by constructing 16-bit, 32-bit and 64-bit indexes. Using 64-bit CPUs, we find that 64-bit indexes are slightly faster than 32-bit indexes despite being nearly twice as large.
Adresse de la version officielle :	http://www.sciencedirect.com/science/article/pii/S...
Déposant:	Lemire, Daniel
Responsable :	Daniel Lemire
Dépôt :	28 juill. 2014 18:32
Dernière modification :	16 juill. 2015 00:46

Actions (connexion requise)

RÉVISER

RÉVISER