Répertoire de publications
de recherche en accès libre
de recherche en accès libre
Lemire, Daniel; Kaser, Owen et Aouiche, Kamel (2010). Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering, 69 (1), 3-28. https://doi.org/10.1016/j.datak.2009.08.006
Fichier(s) associé(s) à ce document :| 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 |
|
RÉVISER |
